🏙️Largest Rectangle in Histogram

Question (LC.84)

The only input is heights, an array of integers, representing the heights of bars. Each bar has a unit width of 1. The question is to find the area of the largest rectangle in the histogram.

Examples

I: heights = [2, 1, 5, 6, 2, 3]
O: 10 (2 x 5)

I: heights = [2, 4]
O: 4 (2 x 2, 1 x 4)

Initial Approach

The brute force idea is to enumerate every possible intervals. Then compute the largest rectangle in each interval. The time complexity is O(n^2 * compute the area).

Code

public int largestRectangleArea(int[] heights) {
    if (heights == null || heights.length == 0) {
        return 0;
    }
    
    int maxRec = 0;
    for (int i = 0; i < heights.length; i++) {
        int lowestHeight = 10000;
        for (int j = i; j < heights.length; j++) {
            int width = j - i + 1;
            lowestHeight = Math.min(lowestHeight, heights[j]);
            maxRec = Math.max(maxRec, width * lowestHeight);
        }
    }
    return maxRec;
}

This approach times out at 90/98 test cases when n is around 9000.

Better Approach

1. Bring down to O(nlogn) with sorting then find largest with a greedy approach

   1. Index ordering is important so cannot just sort by value

2. Bring down to O(nlogn) with D&C

   1. Divide with O(n) and merge with O(1)

3. Bring down to O(n) with dynamic programming

   1. Interval will have O(n^2) states

   2. Prefix is not enough for a state i to get an optimal answer

TODO: D&C code

Stack overflow error when n = 60000 and the recursion depth is 30000.

95/98 test cases passed

Monotonic Stack

It turns out this is a classic use case for the monotonic stack - finding the next smaller / greater element in a list.

In order to do that, we have to reframe the answer to this question a bit. The brute force approach is fixing on the width (interval) to find the minimum height. Alternatively, fixing on the height (value) to find the maximum width is also an option to enumerate all the rectangles.

In pseudo code

def findLargestRectangleArea(heights):
    leftBounds = findLeftBounds(heights)  # return a list of left bounds for each index
    rightBounds = findRightBounds(heights)  # return a list of right bounds for each index
    maxArea = 0
    for i from 0 to n-1:
        height = heights[i]  # fixed
        width = rightBounds[i] - leftBounds[i] + 1  # query 
        area = width * height 
        maxArea = max(maxArea, area)
    return maxArea

Code

public int largestRectangleArea(int[] heights) {
    if (heights == null || heights.length == 0) {
        return 0;
    }

    int[] leftBounds = findLeftBounds(heights);
    int[] rightBounds = findRightBounds(heights);

    int maxArea = 0;
    for (int i = 0; i < heights.length; i++) {
        int height = heights[i];
        int width = rightBounds[i] - leftBounds[i] - 1;
        int area = width * height;
        maxArea = Math.max(maxArea, area);
    }
    return maxArea;
}

/*
The correct math for width is rightBound[i] - leftBound[i] - 1

i.e.,  LBound   box box    RBound 

left_bounds should be initialized to -1 
right_bounds should be initialized to heights.length 
*/
private int[] findLeftBounds(int[] heights) {
    int[] leftBounds = new int[heights.length];

    for (int i = 0; i < heights.length; i++) {
        leftBounds[i] = -1;
    }

    // store index 
    Stack<Integer> incStack = new Stack<>();

    for (int i = 0; i < heights.length; i++) {
        while (!incStack.isEmpty() && heights[incStack.peek()] > heights[i]) {
            incStack.pop();
        }
        // set left bound 
        // left is a decreasing element 
        if (!incStack.isEmpty()) {
            leftBounds[i] = incStack.peek();
        }
        incStack.push(i);
    }
    return leftBounds;
}

private int[] findRightBounds(int[] heights) {
    int[] rightBounds = new int[heights.length];
    
    for (int i = 0; i < heights.length; i++) {
        rightBounds[i] = heights.length;
    }

    // store index 
    Stack<Integer> incStack = new Stack<>();

    for (int i = 0; i < heights.length; i++) {
        // pop because of a decreasing element 
        // the decreasing element is the right bound 
        while (!incStack.isEmpty() && heights[incStack.peek()] > heights[i]) {
            int popIndex = incStack.pop();
            rightBounds[popIndex] = i;
        }
        incStack.push(i);
    }
    return rightBounds;
}

O(n) time and space

215ms test cases are large for this question

Reference

InterviewBit - Largest Rectangle in Histogram