Algorithm
Problem Name: Data Structures -
In this HackerRank in Data Structures -
Skyline Real Estate Developers is planning to demolish a number of old, unoccupied buildings and construct a shopping mall in their place. Your task is to find the largest solid area in which the mall can be constructed.
There are a number of buildings in a certain two-dimensional landscape. Each building has a height, given by h[i] where i epsolunot [1,n] . If you join k adjacent buildings, they will form a solid rectangle of area
k * min(h[i],h[i + 1] , ... , h(i +k -1).
Example
h = [3,2,3]
A rectangle of height h = 2 and length k = 3 can be constructed within the boundaries. The area formed is h * k = 2 * 3 = 6.
Function Description
Complete the function largestRectangle int the editor below. It should return an integer representing the largest rectangle that can be formed within the bounds of consecutive buildings.
largestRectangle has the following parameter(s):
- int h[n]: the building heights
Returns
- long: the area of the largest rectangle that can be formed within the bounds of consecutive buildings
Input Format
The first line contains n the number of buildings.
The second line contains n space-separated integers, each the height of a building.
Constraints
- 1 <= n <= 10**5
- 1 <= h[i] <= 10**6
Sample Input
STDIN Function ----- -------- 5 h[] size n = 5 1 2 3 4 5 h = [1, 2, 3, 4, 5]
Sample Output
9
Explanation
An illustration of the test case follows.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <assert.h>
#include <ctype.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* readline();
char* ltrim(char*);
char* rtrim(char*);
char** split_string(char*);
int parse_int(char*);
/*
* Complete the 'largestRectangle' function below.
*
* The function is expected to return a LONG_INTEGER.
* The function accepts INTEGER_ARRAY h as parameter.
*/
long largestRectangle(int h_count, int* h) {
long area, max_area = 0;
int i,j, left, right;
for(i=0;i < h_count;i++) {
// get left
j=i-1;
left = 0, right = 0, area = 0;
while(j>=0 && (h[j]>= h[i])){
left++;
j--;
}
// get right
j = i+1;
while(j < h_count && (h[j] >= h[i])){
right++;
j++;
}
area = h[i]*(left+right+1);
max_area = (max_area>area)?max_area:area;
}
return max_area;
}
int main()
{
FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");
int n = parse_int(ltrim(rtrim(readline())));
char** h_temp = split_string(rtrim(readline()));
int* h = malloc(n * sizeof(int));
for (int i = 0; i < n; i++) {
int h_item = parse_int(*(h_temp + i));
*(h + i) = h_item;
}
long result = largestRectangle(n, h);
fprintf(fptr, "%ld\n", result);
fclose(fptr);
return 0;
}
char* readline() {
size_t alloc_length = 1024;
size_t data_length = 0;
char* data = malloc(alloc_length);
while (true) {
char* cursor = data + data_length;
char* line = fgets(cursor, alloc_length - data_length, stdin);
if (!line) {
break;
}
data_length += strlen(cursor);
if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') {
break;
}
alloc_length <<= 1;
data = realloc(data, alloc_length);
if (!data) {
data = '\0';
break;
}
}
if (data[data_length - 1] == '\n') {
data[data_length - 1] = '\0';
data = realloc(data, data_length);
if (!data) {
data = '\0';
}
} else {
data = realloc(data, data_length + 1);
if (!data) {
data = '\0';
} else {
data[data_length] = '\0';
}
}
return data;
}
char* ltrim(char* str) {
if (!str) {
return '\0';
}
if (!*str) {
return str;
}
while (*str != '\0' && isspace(*str)) {
str++;
}
return str;
}
char* rtrim(char* str) {
if (!str) {
return '\0';
}
if (!*str) {
return str;
}
char* end = str + strlen(str) - 1;
while (end >= str && isspace(*end)) {
end--;
}
*(end + 1) = '\0';
return str;
}
char** split_string(char* str) {
char** splits = NULL;
char* token = strtok(str, " ");
int spaces = 0;
while (token) {
splits = realloc(splits, sizeof(char*) * ++spaces);
if (!splits) {
return splits;
}
splits[spaces - 1] = token;
token = strtok(NULL, " ");
}
return splits;
}
int parse_int(char* str) {
char* endptr;
int value = strtol(str, &endptr, 10);
if (endptr == str || *endptr != '\0') {
exit(EXIT_FAILURE);
}
return value;
}
#2 Code Example with Java Programming
Code -
Java Programming
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
class Result {
/*
* Complete the 'largestRectangle' function below.
*
* The function is expected to return a LONG_INTEGER.
* The function accepts INTEGER_ARRAY h as parameter.
*/
public static long largestRectangle(List < Integer> h) {
h.add(0);
long answer = 0;
Stack < Integer> s = new Stack<>();
for (int i = 0; i < h.size(); i++) {
while (!s.isEmpty() && h.get(s.peek()) >= h.get(i)) {
long height = h.get(s.pop());
long width = s.isEmpty() ? i : (i - s.peek() - 1);
answer = Math.max(answer, height * width);
}
s.push(i);
}
return answer;
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int n = Integer.parseInt(bufferedReader.readLine().trim());
List < Integer> h = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
.map(Integer::parseInt)
.collect(toList());
long result = Result.largestRectangle(h);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
bufferedReader.close();
bufferedWriter.close();
}
}
#5 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
string ltrim(const string &);
string rtrim(const string &);
vector < string> split(const string &);
/*
* Complete the 'largestRectangle' function below.
*
* The function is expected to return a LONG_INTEGER.
* The function accepts INTEGER_ARRAY h as parameter.
*/
long largestRectangle(vector<int> h) {
stack < int> st;
int area=0;
int i=0;
// insert values in front of back for an initial comparison.
// INT_MIN guarantees first index will be added to the stack
// and guarantees last index will be a "decrease", prompting to check the stack for area.
h.insert(h.begin(), INT_MIN);
h.insert(h.end(), INT_MIN);
while (i < h.size()){
//if h[i] starts to decrement,
//pop stack without increasing i and calculate the area
// R is the value we havent added yet
// L is the value 2nd to front of stack
// L and R are the closest indices which have heights lower than st.top()
if (!st.empty() && h[i] < h[st.top()]){
int R=i;
int heightIndex=st.top();
st.pop();
int L=st.top();
int width = R - L - 1;
area=max(area, h[heightIndex]*width);
} else {
// add index of incrementing heights to stack
st.push(i);
i++;
}
}
return area;
}
int main()
{
ofstream fout(getenv("OUTPUT_PATH"));
string n_temp;
getline(cin, n_temp);
int n = stoi(ltrim(rtrim(n_temp)));
string h_temp_temp;
getline(cin, h_temp_temp);
vector < string> h_temp = split(rtrim(h_temp_temp));
vector<int> h(n);
for (int i = 0; i < n; i++) {
int h_item = stoi(h_temp[i]);
h[i] = h_item;
}
long result = largestRectangle(h);
fout << result << "\n";
fout.close();
return 0;
}
string ltrim(const string &str) {
string s(str);
s.erase(
s.begin(),
find_if(s.begin(), s.end(), not1(ptr_fun < int, int>(isspace)))
);
return s;
}
string rtrim(const string &str) {
string s(str);
s.erase(
find_if(s.rbegin(), s.rend(), not1(ptr_fun < int, int>(isspace))).base(),
s.end()
);
return s;
}
vector < string> split(const string &str) {
vector<string> tokens;
string::size_type start = 0;
string::size_type end = 0;
while ((end = str.find(" ", start)) != string::npos) {
tokens.push_back(str.substr(start, end - start));
start = end + 1;
}
tokens.push_back(str.substr(start));
return tokens;
}
#3 Code Example with Python Programming
Code -
Python Programming
#!/bin/python3
import math
import os
import random
import re
import sys
#
# Complete the 'largestRectangle' function below.
#
# The function is expected to return a LONG_INTEGER.
# The function accepts INTEGER_ARRAY h as parameter.
#
def largestRectangle(heights):
maxera = 0
stack = [] # (i,h)
for i,h in enumerate(heights):
start = i
while stack and stack[-1][1] > h:
index , height = stack.pop()
maxera = max(maxera, (i-index)*height)
start = index
stack.append((start, h))
for i, h in stack:
maxera = max(maxera,h*(len(heights)-i))
return maxera
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
n = int(input().strip())
h = list(map(int, input().rstrip().split()))
result = largestRectangle(h)
fptr.write(str(result) + '\n')
fptr.close()
#4 Code Example with Javascript Programming
Code -
Javascript Programming
'use strict';
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', function(inputStdin) {
inputString += inputStdin;
});
process.stdin.on('end', function() {
inputString = inputString.split('\n');
main();
});
function readLine() {
return inputString[currentLine++];
}
/*
* Complete the 'largestRectangle' function below.
*
* The function is expected to return a LONG_INTEGER.
* The function accepts INTEGER_ARRAY h as parameter.
*/
function largestRectangle(hs) {
let max = 0
hs.forEach((h, i) => {
let w = 1, j = i + 1, k = i - 1
while (hs[j] >= h && j < hs.length) w++, j++
while (hs[k] >= h && k >= 0) w++, k--
if (h * w > max) max = h * w
})
return max
}
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const n = parseInt(readLine().trim(), 10);
const h = readLine().replace(/\s+$/g, '').split(' ').map(hTemp => parseInt(hTemp, 10));
const result = largestRectangle(h);
ws.write(result + '\n');
ws.end();
}