Largest Rectangle – Part 1

histogramOn and off, during the past couple days I spent time soling the Largest Rectangle challenged form HackerRank (https://www.hackerrank.com/challenges/largest-rectangle). The challenge is described as follows:

“There are N buildings in a certain two-dimensional landscape. Each building has a height given by h in [1 : N]. If you join K adjacent buildings, they will form a solid rectangle of area K * min(h, … , h). Given N buildings, find the greatest such solid area formed by consecutive buildings”.

For a full description of the challenged and additional information regarding constrains and input data, please visit the HackerRank web site.

After reading the description a few times to understand what is required and making sure all the constraints are taken into account a O(n^2) solution come up to mind. The following diagram illustrates my initial thought process (please disregard the shaded areas at this time):

largest_rectangle_overview

Following is the input data which matches the previous diagram:

9

4 3 2 1 2 3 4 4 5

Following is a screen capture of the console of the Eclipse IDE using the given input:

9

4 3 2 1 2 3 4 4 5

12

The initial idea is to take the first rectangle (height[0] == 4) and set the current maxArea = 4. We then go to the second rectangle (height[1] == 3). At this point the area from the first two rectangles is 3 * 2 = 6. This is illustrated by the first shaded area covering the first two buildings. The important item to understand is that for the first building the height was 4. For the first 2 buildings the common area is determined by the min(height[0], height[1]) * 2. This area is larger than 4 so we update the maxArea and set it to 6.

If we take the first 3 buildings (as illustrated by the additional shared area) we now have a minHeight of (height[0], height[1], height[2]) == min(4, 3, 2) or better yet min((min(height[0], height[1]), min(height[2])) == min(min(4, 3), 2) == min(3, 2) == 2. The width is now 3. The area == 2 * 3 = 6. Given that the area not greater than the previous one (6), there is no reason to update the maxArea and it remains 6.

When we take height[3] into account, it is worth noting that the heights of all current buildings area = 1 * (3 – 0 + 1) = 4. All previous computations can now be ignored when we move forward and start with the next set height[4] == 2.

A solution could be implemented with two loops (and additional minimal code) as illustrated by the following incomplete pseudo code:

for (int i = 0; i < height.length; i++) {

::::

for (int j = i; j < height.length; j++) {

::::

}

}

That is what I aimed for. Implemented the code and gave it a try. The solution needed to pass 14 unit tests. It only passed the first eight and failed (timeout) the last six. Tried a few things and then took a look at the discussions for inspiration. It seemed that other had successfully tried the O(n^2) approach in several programming languages and some passed. Perhaps Java is not fast enough when compared to C or C++.  I do not like to copy code (solutions). I always like to get inspiration by the comments and avoid looking at the implementation code.stack

My next approach was to search for inspiration on the www using Google Chrome. Apparently this problem, under different names and constraints, has been around for decades. I looked at the text of an approach that runs on O(NlogN) and uses a stack. My initial approach did not use a stack. I was not able to find good descriptions even though I ran into text, tutorials and even videos solving this challenge.

The idea as illustrated in my first approach is correctly based on the computations for the area of the largest rectangle in a set of buildings separated by the ones with height[i] == 1. So how the necessary information could be better managed? The area is based on the height * length. The height is represented by the largest minimum in a segment defined by some i and j.

Following is my solution which was passed all 14 tests using Java:

package john.canessa.largest.rectangle;

import java.util.Scanner;

import java.util.Stack;

public class Solution {

static int    line   = 1;

/*

* show stack

*/

static String  showStack(Stack<Integer> stack) {

String s = “[” + line++ + “] stack: “;

if (stack.isEmpty()) {

s += “X “;

}

for (Integer i : stack) {

s += (i + ” “);

}

return s;

}

/*

* find max area in array of heights using stack

*/

static int getMaxArea(int[] height) {

int maxArea   = 0;

int top              = 0;

int area      = 0;

int i         = 0;

// **** create empty stack ****

Stack<Integer> stack = new Stack<Integer>();

// **** for every building height ****

while (i < height.length) {

// **** if stack is empty or height[i] is higher than the bar at top of stack ****

if (stack.isEmpty() || (height[i] > height[stack.peek()])) {

stack.push(i++);

// **** ****

} else {

// **** ****

top = stack.pop();

// **** calculate the area with height[top] stack as smallest bar

area = height[top] * (stack.empty() ? i : i – stack.peek() – 1);

// **** update the max area (if needed) ****

if (area > maxArea) {

maxArea = area;

}

}

// **** display the stack ****

System.out.println(showStack(stack) + “area: ” + area + ” maxArea: ” + maxArea + ” i: ” + i);

}

System.out.println(“—- —- —-“);

// **** process the contents in the stack ****

while (!stack.isEmpty()) {

top = stack.pop();

// **** ****

if(!stack.isEmpty()) {

System.out.println(“top: ” + top + ” peek: ” + stack.peek());

} else {

System.out.println(“top: ” + top + ” i: ” + i);

}

// **** ****

area = height[top] * (stack.isEmpty() ? i : i – stack.peek() – 1);

// **** update the max area (if needed) ****

if (area > maxArea) {

maxArea = area;

}

// **** display the stack ****

System.out.println(showStack(stack) + “area: ” + area + ” maxArea: ” + maxArea + ” i: ” + i);

}

// **** ****

return maxArea;

}

/*

* test code

*/

public static void main(String[] args) {

// **** read building heights ****

Scanner sc    = new Scanner(System.in);

Int N         = sc.nextInt();

int[] h              = new int[N];

for (int n = 0; n < N; n++) {

h[n] = sc.nextInt();

}

// **** compute and display max area ****

System.out.println(getMaxArea(h));

// **** close scanner ****

sc.close();

}

}

There are tree methods. The main() method implements the test code. It loads the array with the building heights, The showStack() method is used to build a string with the contents of the stack. The actual solution is implemented in the getMaxArea() method.

Following is a screen capture of the console of the Eclipse IDE:

9

4 3 2 1 2 3 4 4 5

[1] stack: 0 area: 0 maxArea: 0 i: 1

[2] stack: X area: 4 maxArea: 4 i: 1

[3] stack: 1 area: 4 maxArea: 4 i: 2

[4] stack: X area: 6 maxArea: 6 i: 2

[5] stack: 2 area: 6 maxArea: 6 i: 3

[6] stack: X area: 6 maxArea: 6 i: 3

[7] stack: 3 area: 6 maxArea: 6 i: 4

[8] stack: 3 4 area: 6 maxArea: 6 i: 5

[9] stack: 3 4 5 area: 6 maxArea: 6 i: 6

[10] stack: 3 4 5 6 area: 6 maxArea: 6 i: 7

[11] stack: 3 4 5 area: 4 maxArea: 6 i: 7

[12] stack: 3 4 5 7 area: 4 maxArea: 6 i: 8

[13] stack: 3 4 5 7 8 area: 4 maxArea: 6 i: 9

—- —- —-

top: 8 peek: 7

[14] stack: 3 4 5 7 area: 5 maxArea: 6 i: 9

top: 7 peek: 5

[15] stack: 3 4 5 area: 12 maxArea: 12 i: 9

top: 5 peek: 4

[16] stack: 3 4 area: 12 maxArea: 12 i: 9

top: 4 peek: 3

[17] stack: 3 area: 10 maxArea: 12 i: 9

top: 3 i: 9

[18] stack: X area: 9 maxArea: 12 i: 9

12

In order to better follow the algorithm, the showStack() method displays a line number. Now let’s discuss the output line by line to get a good understanding of the algorithm.

Line 1. The stack is empty. We push i (not height[i]) so we have the left index for the width of the first rectangle.

[1] stack: 0 area: 0 maxArea: 0 i: 1

Line 2. We pop the top of the stack which holds 0. The height[0] == 4. The area is calculated as area = 4 * 1 = 4. The maxArea is now set to maxArea = area = 4. This makes sense since the height of the first bar is 4.

[2] stack: X area: 4 maxArea: 4 i: 1

Line 3. The stack is now empty so we push i == 1.

[3] stack: 1 area: 4 maxArea: 4 i: 2

A new area has not been computed and I has been incremented by 1 so it is now set to i = 2.

Line 4. The next (and only value) in the stack is popped so top = 1. The area for the min rectangle (in this case height[1] == 3) is computed as area = 3 * I which results in area = 3 * 2 = 6. Given that area == 6 is greater than maxArea == 4 the maxArea is set to maxArea = area = 6.

[4] stack: X area: 6 maxArea: 6 i: 2

Line 5. With an empty stack, we push i == 2 and increment i = 3.

[5] stack: 2 area: 6 maxArea: 6 i: 3

Line 6. We pop the top of the stack which holds top = 2 and compute the area of the rectangle area = height[2] * 3 which produces area = 2 * 3 = 6. Given that area == 6 is equal to maxArea == 6 the maxArea is not updated.

[6] stack: X area: 6 maxArea: 6 i: 3

Line 7. The stack is empty so we push i = 3 and then increment i to i== 4;

[7] stack: 3 area: 6 maxArea: 6 i: 4

Line 8. The stack is not empty and the height[4] = 2 > height[3] = 1 so we push i = 4 and increment i = 5. Note that the stack now holds the indices 3 and 4 to height[3] == 1 and height[4] == 2.

[8] stack: 3 4 area: 6 maxArea: 6 i: 5

Line 9.  The stack contains 2 entries and the height[5] = 3 > height[4] = 2 so 5 is pushed on to the stack and I is incremented i == 6

[9] stack: 3 4 5 area: 6 maxArea: 6 i: 6

Line 10. The stack now contains 3 entries. The height[6] = 4 > height[5] = 3 so 6 is pushed on to the stack and I is incremented I = 7.

[10] stack: 3 4 5 6 area: 6 maxArea: 6 i: 7

Line 11. The stack is not empty (it contains 4 entries). The height[7] = 4 equals height[6] = 4. We pop the stack and set top = 6. We calculate the area = height[6] == 4 * (i == 7 – 5 – 1) == 4 * (7 – 5 – 1) == 4 * 1 == 4. Given that area == 4 is less than maxArea == 6 the maxArea is left unchanged.

[11] stack: 3 4 5 area: 4 maxArea: 6 i: 7

Line 12. The height[7] == 4 is greater than height[5] == 3 so we push i == 7 and increment I == 8.

[12] stack: 3 4 5 7 area: 4 maxArea: 6 i: 8

Line 13. The height[8] == 5 is greater than the height[7] == 4 we push i == 8 and increment i == 9.

[13] stack: 3 4 5 7 8 area: 4 maxArea: 6 i: 9

At this point we have traversed the height[] array and have pushed into the stack a set of indices into the height[] array. We now process the stack.

Line 14. We pop the stack top == 8. We compute the area = height[top == 8] * (i == 9 – 7 – 1) == 5 * 1 == 5. We have computed the area of the last height. Since area = 5 < maxArea = 6 the value of maxArea is not changed.

top: 8 peek: 7

[14] stack: 3 4 5 7 area: 5 maxArea: 6 i: 9

Line 15. We pop the top of the stack into top = 7. In this case height[7] = 4, stack.peek = 5 and i = 9. The area = 4 * (9 – 5 – 1) == 4 * 3 = 12. The area == 12 > maxArea == 6 so maxArea = 12.

top: 7 peek: 5

[15] stack: 3 4 5 area: 12 maxArea: 12 i: 9

Line 16. We pop the top of the stack into top = 5. In this case the height[5] = 3 and i = 9. The area = 3 * (9 – 4 – 1) = 3 * 4 = 12. The area = 12. The area is equal to maxArea. The maxArea is not updated.

top: 5 peek: 4

[16] stack: 3 4 area: 12 maxArea: 12 i: 9

Line 17. We pop the top of the stack into top = 4. The height[4] = 2 and i = 9. The area = 2 * (9 – 3 – 1) = 2 * 5 = 10. The area = 10 is less than or equal to maxArea = 12. The maxArea is not updated.

top: 4 peek: 3

[17] stack: 3 area: 10 maxArea: 12 i: 9

Line 18. We pop the top of the stack into top = 3. Note that the stack is now empty. The height[3] = 1 and I = 9. The area = 1 * 9 = 9. Area = 9 < maxArea = 12. The maxArea is not updated. Note that what we are computing is the area of the band of height = 1 for the entire array area = height[3] * height.lenght == 1 * 9 = 9. Since area == 9 and maxArea == 12 then the maxArea is not updated.

top: 3 i: 9

[18] stack: X area: 9 maxArea: 12 i: 9

At this point the loop exits since the stack is now empty. The maxArea variable holds the value of 12 which is displayed by the main() method.

This algorithm is not simple and requires a considerable amount of time to understand and come up with.

If you have comments or questions regarding this entry or any other entry in this blog, please send me a message via email.

John

john.canessa@gmail.com

Leave a Reply

Your email address will not be published. Required fields are marked *