Largest Rectangle – Part 2

daveed_vandevoordeI received a message regarding the Largest Rectangle – Part 1 post. It seems that like in many other blogs and posts, I failed to properly describe the algorithm. It seems that I was just describing the implementation. Sorry about that. Thanks for the comment xxx (will not disclose names unless explicitly indicated in email messages). I will attempt to address my mistake in this new post.

The following diagram illustrates the histogram / set of buildings that we will use as an example:largest_rectangle_2

The view of the stack associated with the height[] array is illustrated in the following figure:largest_rectangle_stack

With these two items, I will now describe the operation and not the code which is listed towards the end of this post.

The algorithm uses a stack to keep in order the indices to the height[] array which holds the actual heights of the buildings. The idea is to push indices as long as they are greater than the predecessor height. As soon as a smaller building is encountered, the task is to compute the area of the rectangle backwards updating the maxArea as needed. It is quite interesting to note how the indices are updated and used for the computations.

Hopefully the stack diagram and the code in this post are of help.

Following is the output from the Eclipse IDE console using the data illustrated in the first figure:

9

1 2 3 2 1 5 8 7 1

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

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

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

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

[4] stack: 0 area: 4 maxArea: 4 i: 3

[5] stack: 0 3 area: 4 maxArea: 4 i: 4

[6] stack: 0 area: 6 maxArea: 6 i: 4

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

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

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

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

[11] stack: 4 5 area: 8 maxArea: 8 i: 7

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

[13] stack: 4 5 area: 14 maxArea: 14 i: 8

[14] stack: 4 area: 15 maxArea: 15 i: 8

[15] stack: X area: 8 maxArea: 15 i: 8

The Java code follows:

package john.canessa.largest.rectangle;

import java.util.Scanner;

import java.util.Stack;

public class Solution {

// **** displayed line number ****

static int    line   = 0;

/*

* 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 an integer stack (holds indices from height[]) ****

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] as smallest height ****

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();

}

}

I did some research regarding how this brilliant and clean algorithm was developed. Apparently the algorithm was invented in 1992 by Daveed Vandevoorde for finding the largest uniform rectangle in a 2D array of boolean values. It does so, however, using a stepwise approach that teaches general algorithm improvement techniques. So while the algorithm itself has apparently become quite popular among practitioners of computer vision, the article still generates a lot of interest from computer science teachers.

If you have comments or questions on this or any other post in this blog, please send me a message via email. I will not disclose your name unless you explicitly state so.

John

john.canessa@gmail.com

Follow me on twitter:  @john_canessa

Leave a Reply

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