I 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:
The view of the stack associated with the height[] array is illustrated in the following figure:
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