- Practice
- Data Structures
- Stacks
- Largest Rectangle
- Discussions

# Largest Rectangle

# Largest Rectangle

JimB6800 + 10 comments To Moderator: Most of the other problems in the data structures area are regarding fundamental use of the data structure. I believe that this problem would be more appropriately located in the Algorithms section as it assumes development of an algorithm based on a stack. From the problem description, and from a number of the discussion comments, it's not clear to many how a stack would be used to solve this problem.

I suggest either 1) move to algorithms section, or 2) describe the algorithm in enough detail such that this becomes a stack development/usage problem.

SidWagz + 1 comment I agree because my solution was a simple divinde and conquer with recursion and I could not think In anyway I would use stacks.

brynn_mahsman + 6 comments If you're doing recursion you're using a stack, specifically the call stack.

mkhan31995 + 1 comment Will you please explain ? Thank You

mfilandro + 1 comment I belive what Brynn is saying is that the process of recursion creates a stack whether or not you are using a stack data structure to store data.

Basically, each time you recurse, you're putting the current call of the function on hold and making a new call to the function. Then, once you hit the base case, you start going down the list of functions in a Last In, First Out manner, because the VM has created a stack of your function calls to process later while you were recursing.

mkhan31995 + 0 comments Thanks. It's clear to me now.

3r4b6wgzr0650 + 1 comment According to this logic all problems should be listed under "Stack" section, because stack is implicitly used every time you call a function.

M_F_H + 1 comment No, the thing is that this problem is "naturally" solved using stack

*without recursion*, in iterative manner: you go linearly over the h[i] and push candidates on the stack and pop them off depending on rise or decrease of height. You*can*solve it with recursion, but then as it has been said you replace that stack by the recursion stack. (Yet it's not natural, I wonder how you do it correctly, because you may have to "glue together"rectangles of same height from the left and the right, and it might happen than a "left part" and "right part" of a smaller rectangle would have been dropped in the sub-problems but together they give more than the the "larger rectangles" individually...)M_F_H + 0 comments consider h[i] = 1 for i=0..5, = 3 for i=6..8, =2 for i=9..11, =1 for i=12.

Then your divide & conquer solution should find 3(width)x3(height) for the left part, 3(width)x2(height) for the right part, end even if it glues together these two and finds that this can give a 6(width)x2(height) = 12 rectangle, how can it take into account the 9x1 rectangle left + 4x1 rectangle right which give 13 ? Unless your sub-problem solver returns a whole list of rectangles for the left and for the right part and then checks how they can be glued together... Then actually you do in a more complicated way the same what can be done with a stack in a single linear run.

mahawarrahul51 + 0 comments well said!!!

mahipalsaran + 0 comments then all recursion problem should be in stack section,am i right?

xdavidliu + 0 comments I can't tell if this comment is serious, but if it is; clearly using recursion, which incidentally creates a call stack, surely shouldn't count as using the stack data structure, which this problem is listed under.

damoliaarvind + 1 comment What you think about using DP ....?

vickaboy + 1 comment cant use dp as 2d matrix size will be more than allow memory, it passes some of the test cases though however abort is being called on other.

damoliaarvind + 0 comments that why i got sucks.... thanks buddy.. :)

ubbnz + 2 comments I used stack to keep track of heights. You can have look on my github https://github.com/ubbn/HackerRank/blob/master/datastructure/stacks/largestrectangle/Solution.java

Edit: Yes, not cumulative. Wording is corrected

tranc2606 + 4 comments Heights are not cumulatively increasing, that would make the problem so much easier, and yes, a stack could be used in that case. I took a look at test#2 and this is the input:

10 6320 6020 6098 1332 7263 672 9472 28338 3401 9494

output:18060 (from adding the first three numbers)

I also looked at another test, and the rectangle can be in the middle, it doesn't neccessarily have to be on the extremes.

ZenoMachine + 0 comments Why is it not 28338? 28338 > 18060

thebick + 1 comment The correct answer is 28838. If you have 18060, your algorithm is buggy. (I just passed the challenge, then put your example in and got 28838)

On the other hand, your example helped me find the last bug that was stopping me.

msahu6174 + 0 comments Do you mean 28338 as answer. Simple stare at the sequence reveals that answer should be 28338. The larest one.

abinashhota95 + 0 comments 2838 not 28338

xdavidliu + 0 comments you misunderstood his comment; the stack keeps track of

*subsequences*that are increasing. This is a necessary part of the optimal O(N) solution.

xdavidliu + 0 comments this is the optimal O(N) solution

tranc2606 + 2 comments I totally agree. The only solution I have been able to see so far using a stack is very hairy. A hint would be appreciated.

harsimransingh31 + 0 comments # include

using namespace std;

class hell { int n,*a; long long int ar=0; public: void get() { cin>>n; a=new int(n); for(int i=0;i>a[i]; } for(int i=0;iar) ar=temp; } } cout<

int main() { hell q; q.get(); return 0; }

bennattj + 13 comments Look at the picture below which pretty much shows the cases you need to consider.

Basically, we're going to start with

**building 1**, then compute all of the areas of each rectangle and choose the maximum from that. Notice that when we start with**building 1**, we have no idea when the end of it's rectangle will be (represented by a dashed arrow going to the right). The next thing you should notice is that if the next building goes up (higher than the previous), all active areas will remain active (i.e. we still haven't found the end of the area).When

**building 5**is added, it definitely ends the previous building's area (or whatever area it was part of) and, in this case, that's it. Also notice that we need to extend**building 5***back*through**building 4**. How do you know to stop at**building 4**? Easy, the next active area (coming from**building 3**) has a height*lower*than**building 5**'s, so that area is still active (in other words it will go through**building 5**).Hopefully you're starting to see how a stack can be used here: when the next building is taller than the previous, add it to the stack (to be processsed later). When the next building is shorter: pop off stack until you find a starting area with a smaller height (than the current building) or you empty the stack (meaning it goes all the way back through the first building). Now push this building's height along with it's left position onto the stack.

When you pop off the stack, this means you've found the right side of an area, so compute its area and see if it's the maximum.

*Also*when you find the "left wall" for the current building (meaning you found a smaller building in the stack or went all the way back to the first building), you need to remember that position*in addition to*the height of the current building so that when the current building is eventually popped off of the stack, you can properly compute it's area. Notice how**building 6**extends both backwards and forwards, such that when I get to**building 8**, I have to know that**building 6**'s height extended all the way back through**building 2**.m_kaleia + 0 comments Thanks a lot for clarifying the problem, your example should be considered the main test case instead of the original one

Cheers

codeeater + 0 comments thanks

devinludwig + 0 comments Here's a ruby implementation:

def largestRectangle(h) max, stack = 0, [[h[0],0]] for i in 1...h.size if h[i]>h[i-1] stack.push [h[i],i] else l2=nil while stack.any? and stack[-1][0]>h[i] l = stack.pop l2 = l[1] max = [max, l[0]*(i-l[1])].max end stack.push [h[i], l2 ? l2 : i] end end stack.each{|b| max = [max, b[0]*(h.size-b[1])].max} max end

vipulvikram + 0 comments Nice explanation.

jonnymcgow7 + 0 comments Awesome explanation, for anyone that is still confused on this problem, consider unlocking the editorial. The explanation there is very well written as well.

Abhishek113 + 0 comments I am not getting it. WIll you please give an explainantion with the test case other that given test case?

Abhishek113 + 0 comments what is the ans for this test case:

10 8979 4570 6436 5083 7780 3269 5400 7579 2324 2116

ayushr2 + 6 comments Thank you so much for explaining! Made it really clear! Here is my python implementation:

def largestRectangle(h): s = [] ans = len(h) h.append(0) for i in range(len(h)): left_index = i while len(s) > 0 and s[-1][0] >= h[i]: last = s.pop() left_index = last[1] ans = max(ans, h[i] * (i + 1 - last[1])) ans = max(ans, last[0] * (i - last[1])) s.append((h[i], left_index)) return ans

Abhishek113 + 0 comments [deleted]eduasinco + 0 comments [deleted]eduasinco + 0 comments [deleted]eduasinco + 0 comments [deleted]eduasinco + 0 comments [deleted]eduasinco + 0 comments Mine is quite similar but not completely.

def largestRectangle(h): stack = deque() max_area = 0 h += [0,] for i, n in enumerate(h): if not stack or n >= stack[-1][1]: stack.append((i, n)) else: while stack and stack[-1][1] >= n: p = stack.pop() max_area = max((i - p[0])*p[1], max_area) stack.append((p[0], n)) return max_area

atreyvishwas50 + 0 comments Thank you for this great explaination. But I have a question, what if the height of buildings decrease from left to right, for example:

5 4 3 2 1

I think to tackle this problem we use queue.

tat_lim + 0 comments # Java 8 Solution in O(n)

`static long largestRectangle(int[] h) { Stack<int[]> s = new Stack<>(); // Create stack of span = [x0, x1] int n = h.length; h = Arrays.copyOf(h, n+1); // Append a sentinel to array h int x1; int maximum = 0; for(int x0 = 0; x0 <= n; x0++) { for(x1 = x0; !s.isEmpty() && h[s.peek()[0]] >= h[x0]; ) { int[] x = s.pop(); x1 = x[1]; maximum = Math.max(maximum, h[x[0]] * (x0 - x1)); } s.push(new int[]{x0, x1}); } return maximum; }`

sandeepks + 0 comments [deleted]ameya_v_patil + 1 comment Great explanation : Here is my implementation using OOP

`static class Building { public int lb; public int rb; public int height; public int index; Building(int l,int r,int h,int ind) { this.lb=l; this.rb=r; this.height=h; this.index = ind; } public long getArea() { System.out.println("Rectangle : height : " + this.height + "(" + this.lb+" , "+ this.rb+") = " + this.height * (rb-lb)); return this.height * (rb-lb); } } // Complete the largestRectangle function below. static long largestRectangle(int[] h) { Stack<Building> stk = new Stack<>(); long maxArea = 0; Building prevBuilding = new Building(0,-1,h[0],0); stk.push(prevBuilding); for(int i=1;i<h.length;i++) { Building b = new Building(-1,-1,h[i],i); if(b.height > prevBuilding.height) { b.lb = i; stk.push(b); } else { while(!stk.isEmpty() && stk.peek().height >= b.height) { Building stkTop = stk.pop(); stkTop.rb = i; maxArea = Math.max(maxArea,stkTop.getArea()); } // Find current building's lb and add it to the stack if(!stk.isEmpty()) { if(b.height > stk.peek().height) { b.lb = stk.peek().index+1; } else { Building first = stk.pop(); b.lb = first.lb; first.rb= i; maxArea = Math.max(maxArea,first.getArea()); } } else { b.lb = 0; } stk.push(b); } prevBuilding = b; } while(!stk.isEmpty()) { Building b = stk.pop(); if(b.rb<0) { b.rb = h.length; } maxArea = Math.max(maxArea,b.getArea()); } return maxArea; }`

minhdung_dang + 0 comments Nice, here is a Python function that prints out the area:

def largestRectangle(h): h.append(0) stack = [] maxArea = (0, 0, 0, 0) for i, height in enumerate(h): j = i while stack and stack[-1][1] >= height: j, last = stack.pop() area = (i - j) * last if area > maxArea[0]: maxArea = (area, j, i, last) stack.append((j, height)) print maxArea return maxArea[0]

minhdung_dang + 0 comments [deleted]

shubhamchandra + 0 comments [deleted]choito + 5 comments I also agree. It seems this problem is more like an algorithm problem instead of the data structure problem using the stack. I used the dynamic programming to find the maximum possible largest rectangle. For each height, I found the width to the right and left where each rectangle can extend at most. And then, I simply multiplied each height and width and updated the largest rectangle from the first to the last rectangle.

pratyaksh_nidhi + 0 comments How did you divide the problem into 2 or more smaller problems

jain_lalit90 + 1 comment works like a charm! just one question... why is there a need for DP?

shashank9226 + 0 comments The DP approach smiplifies the code to a large extent, if you get the approach. For eg. here the approach is: 1. Get the rectangle for a building (sub-problem) 2. Do it for all the the buildings (recursion or looping) 3. Return the maximum of the lot.

ShubhamV06 + 2 comments I dont get it. This makes the algorithm of O(n^2) right? Correct me if i am wrong. I also did using the same method and can u explain why the stack method would be better than this?

CliffyMk + 0 comments n log n probably

vipulvikram + 0 comments By using stack u can solve it in O(n) time. Here there is concept similar to find the smallest window in a string to find a pattern containg fixed count of some characters. here max iteration time is O(2*n)=O(n).

nishanthsanjeevi + 1 comment i dont find any requirement to use a stack moreover using a stack is a complication to this problem

shashank9226 + 0 comments You are correct. DP with Recursion. Simple.

19998sachinyadav + 0 comments This i O(n^2) aproach. How can we improve this

_miran_ + 0 comments Actually, if you use stack instead of divide and conquer approach, you get solution with better time complexity - O(n).

blairnangle + 0 comments Completely agree. The

*optimal*solution requires using stacks (in the data structure sense) but it is by no means clear from the description of the problem that stacks should be used in the solution.NaruSh + 0 comments Totally agreed. This section should contain problems dealing with Stack manipulation. The Linkedlist section is very well maintained, all the problems revolve around Linkedlist manipulations.

potter0313 + 1 comment I was able to solve without stack and don't see any point where stack would be helpful or improve runtime of the algorithm or save memory space.

M_F_H + 0 comments What are your measurements of runtime and/or memory for recursive vs stack solution? The stack solution is one single loop, if height increases then you may have to do at most one push (not necessarily: only when there are two consecutive strict increases) and if height goes down you

*may*have to do several pops, but not many: because height of stack = total # pushes - total # pops, so in the mean you do less than 1 push*or*1 pop for each i. This is very fast. And you do not need*any*additional memory. While when you use recursion, and on each level of recursion you have list manipulation and return values are lists, this uses lots of memory. Since you have to access each element at least once, anyway, I don't think this can be faster, and will usually be slower.

craig53 + 0 comments I disagree, almost every problem I've encountered here requires you to come up with an algorithm. The coding part is minor once you have algorithm correct. i.e. if you were provided the pseudo-code implementation in any major language would be trivial.

I certainly hope no interviewer would expect you to come up with one of these algorithms on the spot in a 45 minute interview (and then proceed to write code for it). I suspect some would though because once you know the algorithm it seems a lot simpler.

de4thst4lk3r + 1 comment That sample test case isn't so great to help you understand the problem.

AbhishekThecoder + 1 comment Yes, Exactly!! The sample test case is not sufficient enough to understand the problem. I actually understood the problem while reading the discussion.

tgunix + 6 comments italwaysdepends + 1 comment This video was really helpful. Thanks!

juli6 + 0 comments Thanx for the video

Mani4723 + 0 comments thanks

tagaew + 2 comments Thank you for the video! This is the key to the solution. However, it is still not clear to me the formula that is using in the calculation. The guy is explaining the formula, however I can't catch it.

mkhan31995 + 3 comments I faced the same problem my friend. I couldn't get the formula. SO i did a research on it and found a better video which explained me the core of this question. Have a look at it : https://www.youtube.com/watch?v=VNbkzsnllsU

Hope that helped you friend.

Jlookup + 0 comments good video, thanks!

bert5porter + 0 comments Yes, this is a MUCH better video. He explains the algorithm, why it works.

pareksha + 0 comments Hey, thanks !

phillm6 + 0 comments [deleted]

phillm6 + 0 comments *edited I think I found a problem with Tushar Roy's algorithm.

I think this is a telling case: If you have this list (no delimiter) 24534513

list: 24534513 stack:012 i = 3 (push till a decreasing value found)

list: 24534513 stack:012 i=3 (i-p)*list[p] -> (3-2)5 -> (3-1)4 So we update max to 5 then 8, but 2<3 (list[0]

list: 24534513 stack:0 345 i=6 (push until decreasing again)

list: 24534513 stack:0 345 i=6 -> (1)5 -> (2)4 -> (3)3 -> (6)2

So max is 12... but wait, 3 forms the min height of a rectangle starting at 1 and ending at 5 for a total size of 15!

My suggestion is that you check if your previous index (j) skips (has a greater than one difference with the current) and if list[j] is less than our current value (if not, the regular algorithm will take care of it).

sakets594 + 0 comments [deleted]sakets594 + 0 comments [deleted]

akrox58 + 2 comments http://www.informatik.uni-ulm.de/acm/Locals/2003/html/histogram.html

Check this for full description of problem! :)

prashanth_sunder + 0 comments Thanks a lot!

jacob_sthilaire + 0 comments [deleted]

perfectcodder + 2 comments # O(n) with one Stack

stack=[] area=0 i=0 while i<len(h): if not stack or h[stack[-1]]<=h[i]: stack.append(i) i+=1 else: top=stack.pop() area=max(area,h[top]*(i-stack[-1]-1 if stack else i)) while stack: top=stack.pop() area=max(area,h[top]*(i-stack[-1]-1 if stack else i)) return area

jnarayanam1 + 0 comments Awesome! Simple and Elegant...

M_F_H + 0 comments I did roughly the same (in C++). Note that you can avoid to write the final loop (to empty the stack) if you append a 0 to the list of heights at the very beginning. (That 0 height will trigger the same loop.)

thienlongtpct + 0 comments Test 1 has wrong answer. It shoud be 18.

himanhsu54 + 2 comments Test case 1 1 3 5 9 11 Expected output 81 is this right or i am missing something?

alpha_q2 + 0 comments I am getting 18 as answer

aviral_petwal + 1 comment I am getting 18 as a answer. Idon't think 81 is correct.

himanhsu54 + 1 comment but sample test case 2 gives output 81. should i report it. can someone confirm?

aviral_petwal + 1 comment Yep output should be 18. But it is giving 81 as expected output.

himanhsu54 + 0 comments I reported this in Suggest Edit. Thanks.

rajkumar9606 + 2 comments i did'nt use stack.but any how all testcases passed.

#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ long long n,arr[100001],i,j,max,temp=-1,k,count=1,val; cin>>n; for(i=0;i<n;i++){ cin>>arr[i]; } for(i=0;i<n;i++){ val=arr[i]; int cl1=1,cl=1; for(j=i-1,k=i+1;j>=0 || k<n;j--,k++){ if(j>=0 && arr[j]>=val && cl1==1){ count++; }else cl1=0; if(k<n && arr[k]>=val && cl==1){ count++; }else cl=0; if(cl==0 && cl1==0) break; } max=val*count; if(max>temp){ temp=max; } count=1; } cout<<temp; return 0; }

CrapBag0301 + 0 comments [deleted]cellepo + 0 comments This does pass all test cases... but isn't this O(n^2)?

one_off + 0 comments Second sample test case is wrong - expected output is 81 when it should be 18

landonkoo0207 + 2 comments You don't really need any stack to tackle this problem. Just one array holding the heights would be enought. Then you can work out the maximum rectangle as you go through the building heights. My python3 solution with the comments is below:

n = int(input()) h = [int(x) for x in input().split(" ")] # For each element(height) of an array, # 1. Search the continuous buildings to the left # - if continous building is at the same height or taller, increment the count # 2. Seach the continuous buildings to the right # - if continous building is at the same height or taller, increment the count # 3. Calculate the current rectangle area: # - height of the current building * current count # 4. Check if the current area is larger than the current maximum area # When the search finishes print the maximum area acquired. max_area = 0 for i in range(len(h)): cnt = 0 for j in range(i, -1, -1): if h[j] >= h[i]: cnt += 1 else: break for k in range(i+1, len(h)): if h[k] >= h[i]: cnt += 1 else: break area = h[i] * cnt if area > max_area: max_area = area print (max_area)

SuyogD + 0 comments Superb explanation !! I was working in similar way . Good to see I was working in correct direction. @landonkoo0207

ufabianx + 0 comments While elegant, the worst case complexity is still O(N^2).

e.g.

n = 1e5-1 h[i] = 1, i = range(n)

will make your program timeout.

And in the case you would check for that special case, I would use:

h[0] = h[n-1] = rand()

Sort 280 Discussions, By:

Please Login in order to post a comment