Problem:
Given an n sized array of non-negative integers. The array represents a histogram made of width 1 columns. Each array element represent a column with width 1 and height equal to the array element value.Write a function take the array as input, returns the largest rectangle in the histogram.
For Example:
Given array [2,1,5,6,2,3], the largest rectangle in the histogram is made by the column at index 2 and 3, the rectangular made by height 5 column and height 6 column has size 10, so the output is 10.
Solution:
The brutal force solution is to have a 3 layers of for loops. For each starting index i, we exam all the ending index at the right. For a pair of starting and ending index, we loop all the elements to find the minimum then calculate the area. The time complexity is O(N^3).
A better solution is to use divide and conquer. Once we found the index of the minimum height bar in an array, the solution came from 3 cases:
- the largest rectangle in the histogram is (end - start) * height(minIndex)
- the largest rectangle in the histogram is on the left half.
- the largest rectangle in the histogram is on the right half.
In order to find the largest rectangle in the left half and right half, we can find it recursively.
If the height array is random, each left and right half divide most likely happen in the middle, the time complexity is O(NlogN).
If the height array is sorted, each left and right half happens at the edge, the performance degrades to O(N^2).
The best solution is to use a stack to help the calculation. The intuition is, when we scan the height values from left to right, if the height is increasing, we know, for sure, no matter where the the largest rectangle is, read more will only make it larger if not the same. Once the height starts to decrease, we know, for sure, the tallest bar we saw so far won't form a bigger rectangle, so we can register its value as the potential largest rectangle. Once processed the tallest bar, we then look at the second largest bar we saw so far. If the current bar is taller than the second tallest bar, then the sequence is still increasing, we want to read more to see if we can make the rectangle formed by the second tallest bar larger, otherwise, we know for sure the rectangle formed by the second tallest bar won't increase anymore, so we can register the area as the potential largest rectangle. Then we look at the third largest bar.
The algorithm is, as long as the height is increasing, we keep push the index of the height array into a stack. Once the height is decreasing, we pop out all the out of order elements in the stack in order to restore the increasing sequence in the stack. While we pop the out of order elements in the stack, we register the area of the potential largest rectangle. After we added all the height index into the stack and the stack is still not empty, we then know how to calculate the potential largest rectangles.
import java.util.*;
class Solution {
public static void main(String...args) {
int[] histo = new int[] {2,1,5,6,2,3};
System.out.println(maxArea(histo));
}
public static int maxArea(int[] histo) {
int max = -1;
//store the index of height increasing sequences
Stack<Integer> incrSeq = new Stack<>();
incrSeq.push(-1);
for(int i = 0; i < histo.length; i++) {
if(incrSeq.peek() == -1 || histo[incrSeq.peek()] <= histo[i]) {
incrSeq.push(i);
} else {
while(incrSeq.peek() != -1 && histo[incrSeq.peek()] > histo[i]) {
//calculate the hill area bounded by the two descending indexes at left (incrSeq(top - 1)) and right (i)
max = Math.max(max, histo[incrSeq.pop()] * (i - incrSeq.peek() - 1));
}
//now the height increasing sequence is restored, keep pushing
incrSeq.push(i);
}
}
int end = incrSeq.peek();
while(incrSeq.peek() != -1) {
int index = incrSeq.pop();
//clif edge area bounded by the descending indexe at left (incrSeq(top - 1)) and current index (incrSeq(top - 1))
max = Math.max(max, histo[index] * (end - index + 1));
}
return max;
}
}
class Solution {
public static void main(String...args) {
int[] histo = new int[] {2,1,5,6,2,3};
System.out.println(maxArea(histo));
}
public static int maxArea(int[] histo) {
int max = -1;
//store the index of height increasing sequences
Stack<Integer> incrSeq = new Stack<>();
incrSeq.push(-1);
for(int i = 0; i < histo.length; i++) {
if(incrSeq.peek() == -1 || histo[incrSeq.peek()] <= histo[i]) {
incrSeq.push(i);
} else {
while(incrSeq.peek() != -1 && histo[incrSeq.peek()] > histo[i]) {
//calculate the hill area bounded by the two descending indexes at left (incrSeq(top - 1)) and right (i)
max = Math.max(max, histo[incrSeq.pop()] * (i - incrSeq.peek() - 1));
}
//now the height increasing sequence is restored, keep pushing
incrSeq.push(i);
}
}
int end = incrSeq.peek();
while(incrSeq.peek() != -1) {
int index = incrSeq.pop();
//clif edge area bounded by the descending indexe at left (incrSeq(top - 1)) and current index (incrSeq(top - 1))
max = Math.max(max, histo[index] * (end - index + 1));
}
return max;
}
}
The time complexity is O(N) and the space complexity is also O(N).
