Largest Rectangle

Hello World!

Let’s solve the Largest Rectangle problem from HackerRank. You may click on the title to read the problem statement and try it out once. So let’s start.

In this problem, given an array, we need to find the rectangle with largest area. As shown in the figure above, we have 5 numbers, i.e. heights of the buildings. These numbers in the array can be unsorted. Let’s try to come up with a solution.

At first what I did was to consider each element from the array and subtract it from the entire array. For ex, [1, 2, 3, 4, 5], if we consider the element 2, we subtract 2 from each element. The resulting array is [-1, 0, 1, 2, 3]. Now we need to calculate the length of longest positive sequence in this array which is 4. And as we subtracted two from each of the elements, the area would be 4*2=8. Similarly, we’ll get 5, 8, 9, 8, 5 as the areas if we select 1, 2, 3, 4 and 5 respectively.

This solution gave Time Limit Exceeded error. Let’s see why. In the above example, we subtracted 2 from each element in the array. But we don’t need to subtract if the element is smaller than 2. Also, we need contiguous array elements, hence we can just look to the right and left of the chosen element till we encounter a number smaller than the chosen element. We don’t have to traverse the entire array.

So the modified solution is as follows. I considered an element ‘i’, then looked to its right and to its left till I encountered an element smaller than ‘i’. So let’s say we have 3 contiguous elements on left which are larger or equal to ‘i’ and 4 to the right. Hence, we have total 3+7+1=8 contiguous elements with height ‘i’. Hence the area would be 8*i. This method passes all the test cases of the problem.

I’d be happy to listen to more optimized solution to this problem. The code for this problem in Python3 can be found here.