Largest rectangle in histogram

Given a non-negative integer array representing the heights of a list of adjacent bars. Suppose each bar has a width of 1. Find the largest rectangular area that can be formed in the histogram.

Assumptions

• The given array is not null or empty

Examples

• { 2, 1, 3, 3, 4 }, the largest rectangle area is 3 * 3 = 9(starting from index 2 and ending at index 4)

Solution: Iterative Traversal

use a stack to track ascending order

For each index, if it breaks ascending order, pop everything higher or equal to it.

calculate the area:

1. Height = value of top index in stack

2. width = current index - (next index in stack + 1)

Since only higher ones are popped, at one point the lowest height will enter the stack, but it will never be popped by anyone.

At the end of the array, set the height to 0. Pop the last, aka lowest index. Calculate area like above.

Since there is no index left in the stack. set left to 0.

This will set the width to array.length * lowest height.

public int largest(int[] array){
    int result = 0;
    Deque<Integer> stack = new LinkedList<Integer>();
    for (int i = 0; i <= array.length; i++){
        int cur = i == array.length ? 0 : array[i];
        //when stack is no longer ascending, start taking things out
        while(!stack.isEmpty() && stack.peekFirst() >= cur){
            int height = array[stack.pollFirst()];
            int left = stack.isEmpty() ? 0 : array[stack.peekFirst()];
            result = Math.max(result, height * (i - left);
        }
        stack.offerFirst(i);
    }
    return result;
}  

TC: O(N) one traversal, one push pop per element

SC: O(N) worst case: ascending array O(1) average case

Mistake made: forgot the meaning of variables

cur is the value of current index. This is only used to calculate if next index is ascending in value

height needs to be zero for i == array.length to 1. end ascending at n - 1 index 2. pop lowest element for n length max check

left need to be zero when stack is empty for when lowest element is popped, because it means cur element height is the new lowest, thus prev low can go all the way left until 0