Crack the Backend

Problem Statement

You are given an array heights representing a histogram: the i-th bar has height heights[i] and width 1. Return the area of the largest rectangle that can be formed inside the histogram (rectangle must be aligned with the bars; its height is the minimum of the bars it spans).

Key Observations

Idea: For each bar, the largest rectangle using that bar as height extends left and right until we hit a bar shorter than it. So we need, for each index i, the previous smaller and next smaller index (or -1 / n as boundaries).
Monotonic stack (increasing): When we maintain a stack of indices with increasing heights, and we see heights[i] < heights[stack.peek()], then for the popped index p: right boundary = i, left boundary = stack.peek() (or -1 if stack empty). Area = heights[p] * (right - left - 1). Update max area; then push i. Run a final pass to pop remaining indices (right = n).

Approach

High-level: Stack of indices (heights strictly increasing). For i from 0 to n: while stack not empty and heights[i] < heights[stack.peek()], pop p, left = stack.isEmpty() ? -1 : stack.peek(), area = heights[p]*(i - left - 1), update max; push i. Then pop all with right = n.

Steps: Deque st; int max = 0; for (i = 0; i <= n): while (!st.isEmpty() && (i==n || heights[i] < heights[st.peek()])) { p = st.pop(); w = st.isEmpty() ? i : i - st.peek() - 1; max = Math.max(max, heights[p]*w); } if (i<n) st.push(i). return max.

Implementation

Java

public int largestRectangleArea(int[] heights) {
    Deque<Integer> st = new ArrayDeque<>();
    int max = 0, n = heights.length;

    for (int i = 0; i <= n; i++) {
        int h = i == n ? 0 : heights[i];

        while (!st.isEmpty() && heights[st.peek()] > h) {
            int idx = st.pop();
            int w = st.isEmpty() ? i : i - st.peek() - 1;
            max = Math.max(max, heights[idx] * w);
        }

        st.push(i);
    }

    return max;
}

Test Cases

Example 1

Input

heights = [2,1,5,6,2,3]

Expected

10

Explanation

Bars 5,6 form rectangle 2*5=10.

Complexity Analysis

Time: O(n).
Space: O(n) for stack.

Follow-ups

Previous smaller; range queries.