Largest Rectangle in Histogram

Given an array of integers A of size N. A represents a histogram i.e A[i] denotes height of
the ith histogram’s bar. Width of each bar is 1.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

Find the area of largest rectangle in the histogram.

Input Format

The only argument given is the integer array A.

Output Format

Return the area of largest rectangle in the histogram.

For Example

Input 1:
    A = [2, 1, 5, 6, 2, 3]
Output 1:
    10
    Explanation 1:
        The largest rectangle is shown in the shaded area, which has area = 10 unit.

Method:

Maintain a stack that keeps track of the indices of elements that are increasing, when we see an element that is smaller than the top of the stack, we can start calculating the areas. The difficulty is in determining the left bound, after we pop the top of the stack, the left bound can be determined by the current top + 1, because current top is smaller or equal to the element we popped, thus current top + 1 must be greater than or equal to the element we popped.

6 2 5 4 5 (0)

for example, when we are popping 4, the previous 5 is not in the stack because it was already popped, thus the next element in the stack is 2 (index 1), so the left bound is 1 + 1 = 2

Solution:

Time: O(n)
Space: O(n)

public class Solution {
    public int largestRectangleArea(ArrayList<Integer> A) {
        // 6 2 5 4 5
        // index stack
        Deque<Integer> stack = new ArrayDeque<>();
        int area = 0;
        A.add(0);
        for (int i = 0; i < A.size(); i ++) {
            int currentHeight = A.get(i);
            while (!stack.isEmpty() && A.get(stack.peekFirst()) > currentHeight) {
                int height = A.get(stack.pop());
                int left = stack.isEmpty() ? 0 : stack.peekFirst() + 1;
                int width = i - left;
                area = Math.max(area, width * height);
            }
            stack.push(i);
        }
        return area;
    }
}