Largest Rectangle HackerRank Solution

In this Largest Rectangle HackerRank solution, 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 . If you join  adjacent buildings, they will form a solid rectangle of area .

Largest Rectangle HackerRank solution

I will Provide solution in Multiple programming languages for you. If you are not able to find the code in required language then please share in comments so that our team can help you.

Problem Solution in Python

def largestRectangle(h):
stack = [0]
S = 0
maxS = 0
h.append(0)
for i in range(1, len(h)):

if h[i] >= h[stack[-1]]:
stack.append(i)

else:
while stack and h[i] < h[stack[-1]]:
last = stack.pop()
if stack:
S = (i - stack[-1]-1) * h[last]
else:
S = i * h[last]
if  S > maxS:
maxS = S
stack.append(i)

return maxS

Problem Solution in C++

long largestRectangle(vector<int> h) {
vector<int> ps;
vector<int> ns;
stack<int> pst;
stack<int> nst;

pst.push(0);
ps.push_back(-1);
for(int i=1;i<h.size();i++)
{
while(pst.empty()!=true && h[i]<=h[pst.top()])
{
pst.pop();
}
if(pst.empty()==true)
ps.push_back(-1);
else
ps.push_back(pst.top());
pst.push(i);
}

pst.push(h.size()-1);
ps.push_back(-1);
for(int i=h.size()-1;i>=0;i--)
{
while(nst.empty()!=true && h[i]<=h[nst.top()])
{
nst.pop();
}
if(nst.empty()==true)
ns.push_back(h.size());
else
ns.push_back(nst.top());
nst.push(i);
}

reverse(ns.begin(), ns.end());

int res=INT_MIN;
for(int i=0;i<h.size();i++)
{
int curr=h[i];
curr+=(h[i]*(i-ps[i]-1));
curr+=(h[i]*(ns[i]-i-1));
res=max(res,curr);
}
return res;
}

Problem Solution in JavaScript

function largestRectangle(h) {
h.push(0);
let s = [{h: -1, w: 0}];
let item;
let max = 0;
while((item = h.shift()) !== undefined) {
let w = 0;
while(s[s.length - 1].h >= item) {
let left = s.pop();
w += left.w;
max = Math.max(left.h * w, max);
}
s.push({h: item, w: w + 1});
}
return max;
}

Problem Solution in Java

public static long largestRectangle(List<Integer> h) {
long size = h.size();
long max = 0;

for(int i = 0; i < size; i++) {
long w = 1;
Integer is = h.get(i);

for (int j = i + 1; j < size; j++) {
if (is > h.get(j)) {
break;
}
w++;
}

for (int j = i -1; j >= 0; j--) {
if (is > h.get(j)) {
break;
}
w++;
}

long sum = w * is;
if (sum > max) {
max = sum;
}
}

return max;
}

Problem Solution in TypeScript

function largestRectangle(hs: number[]): number {
let result = 0;
for (let i = 0; i < hs.length; i++) {
const h = hs[i];
let w = 1;
for (let j = i + 1; j < hs.length; j++) {
if (hs[j] < h) {
break;
}
w += 1;
}
for (let j = i - 1; j >= 0; j--) {
if (hs[j] < h) {
break;
}
w += 1;
}
result = Math.max(result, h * w);
}
return result;
}
Solve original Problem on HackerRank here. Checkout more HackerRank Problems