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 maxSProblem 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) {
// Write your code here
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