Skip to main content
CodePeetCodePeet
CodePeet 250

Largest Rectangle in Histogram

HARDProblemSolveExternal Links

Description

You are given an array of integers heights where each element represents the height of a bar in a histogram. Every bar has a uniform width of 1 unit.

Your task is to find the area of the largest rectangle that can be formed within the histogram. The rectangle must be composed of contiguous bars, and its height is limited by the shortest bar it spans.

In other words, for any contiguous group of bars, the widest rectangle you can draw inside them has a height equal to the minimum bar height in that group, and a width equal to the number of bars. You want to maximize height × width over all possible contiguous groups.

Examples

Example 1

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

Output: 10

Explanation: Consider bars at indices 2 and 3 with heights 5 and 6. The shortest bar in this group is 5, and there are 2 bars, so the rectangle has area 5 × 2 = 10. No other contiguous group of bars produces a larger rectangle. For example, spanning all 6 bars gives height 1 × width 6 = 6, and spanning bars [5, 6, 2, 3] gives height 2 × width 4 = 8.

Example 2

Input: heights = [2, 4]

Output: 4

Explanation: We can either take bar 0 alone (area = 2 × 1 = 2), bar 1 alone (area = 4 × 1 = 4), or both bars (min height 2 × width 2 = 4). The maximum is 4, achieved by either bar 1 alone or both bars together.

Example 3

Input: heights = [6, 2, 5, 4, 5, 1, 6]

Output: 12

Explanation: Bars at indices 2, 3, and 4 have heights [5, 4, 5]. The minimum height is 4, and there are 3 bars, giving area 4 × 3 = 12. This beats any single tall bar (max single bar = 6 × 1 = 6) and any wider span (e.g., indices 0-4 with min 2 gives 2 × 5 = 10).

Constraints

  • 1 ≤ heights.length ≤ 10^5
  • 0 ≤ heights[i] ≤ 10^4

Editorial

Brute Force - Expand from Each Bar

Intuition

The simplest way to think about this problem is to consider every bar as the height constraint of a potential rectangle. If we fix a bar's height as the rectangle's height, then the rectangle can extend left and right as far as all neighboring bars are at least as tall.

Imagine you are standing at each bar in the histogram and stretching your arms outward. You keep stretching left as long as the bars you touch are at least as tall as the one you're standing on. You do the same to the right. The distance your arms span is the width of the largest rectangle that uses your bar's height.

By doing this for every single bar and keeping track of the maximum area found, we guarantee we have checked all candidates. One of these rectangles must be the answer, because the optimal rectangle is always limited by the height of some specific bar — and we check every bar.

Step-by-Step Explanation

Let's trace through heights = [2, 1, 5, 6, 2, 3]:

Step 1: Fix bar 0 (height 2). Expand left: at boundary, can't go further. Expand right: bar 1 has height 1 < 2, blocked. Width = 1. Area = 2 × 1 = 2. max_area = 2.

Step 2: Fix bar 1 (height 1). Expand left: bar 0 has height 2 ≥ 1, OK. Expand right: bars 2, 3, 4, 5 all have heights ≥ 1. The shortest bar in the entire array is 1, so it reaches all the way. Width = 6. Area = 1 × 6 = 6. max_area = 6.

Step 3: Fix bar 2 (height 5). Expand left: bar 1 has height 1 < 5, blocked. Expand right: bar 3 has height 6 ≥ 5, OK. Bar 4 has height 2 < 5, blocked. Width = 2 (indices 2-3). Area = 5 × 2 = 10. max_area = 10.

Step 4: Fix bar 3 (height 6). Expand left: bar 2 has height 5 < 6, blocked. Expand right: bar 4 has height 2 < 6, blocked. Width = 1. Area = 6 × 1 = 6. Tall but narrow — not better.

Step 5: Fix bar 4 (height 2). Expand left: bar 3 (6 ≥ 2) OK, bar 2 (5 ≥ 2) OK, bar 1 (1 < 2) blocked. Expand right: bar 5 (3 ≥ 2) OK. Width = 4 (indices 2-5). Area = 2 × 4 = 8. Close, but not better than 10.

Step 6: Fix bar 5 (height 3). Expand left: bar 4 (2 < 3) blocked. Width = 1. Area = 3 × 1 = 3.

Result: max_area = 10, achieved by bar 2 (height 5) spanning indices 2-3.

Brute Force — Expanding from Each Bar — For each bar, expand left and right to find the widest rectangle at that bar's height. The window highlights the span of the rectangle being computed.

Algorithm

  1. Initialize max_area = 0
  2. For each bar i from 0 to n-1:
    a. Set width = 1 (the bar itself)
    b. Expand left: move j from i-1 leftward while heights[j] ≥ heights[i], incrementing width each step
    c. Expand right: move j from i+1 rightward while heights[j] ≥ heights[i], incrementing width each step
    d. Compute area = heights[i] × width
    e. Update max_area = max(max_area, area)
  3. Return max_area

Code

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        int maxArea = 0;
        
        for (int i = 0; i < n; i++) {
            int width = 1;
            
            // Expand left while bars are at least as tall
            for (int j = i - 1; j >= 0 && heights[j] >= heights[i]; j--)
                width++;
            
            // Expand right while bars are at least as tall
            for (int j = i + 1; j < n && heights[j] >= heights[i]; j++)
                width++;
            
            maxArea = max(maxArea, heights[i] * width);
        }
        
        return maxArea;
    }
};
class Solution:
    def largestRectangleArea(self, heights: list[int]) -> int:
        n = len(heights)
        max_area = 0
        
        for i in range(n):
            width = 1
            
            # Expand left
            j = i - 1
            while j >= 0 and heights[j] >= heights[i]:
                width += 1
                j -= 1
            
            # Expand right
            j = i + 1
            while j < n and heights[j] >= heights[i]:
                width += 1
                j += 1
            
            max_area = max(max_area, heights[i] * width)
        
        return max_area
class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int maxArea = 0;
        
        for (int i = 0; i < n; i++) {
            int width = 1;
            
            // Expand left
            for (int j = i - 1; j >= 0 && heights[j] >= heights[i]; j--)
                width++;
            
            // Expand right
            for (int j = i + 1; j < n && heights[j] >= heights[i]; j++)
                width++;
            
            maxArea = Math.max(maxArea, heights[i] * width);
        }
        
        return maxArea;
    }
}

Complexity Analysis

Time Complexity: O(n²)

For each of the n bars, we expand left and right. In the worst case (e.g., a sorted ascending array), the expansion from the last bar scans all n-1 previous bars. Across all bars, the total comparisons can reach n × (n-1)/2, giving O(n²).

Space Complexity: O(1)

We only use a constant number of variables (width, area, loop indices). No additional data structures are needed.

Why This Approach Is Not Efficient

The brute force performs O(n²) work in the worst case. With n up to 10^5, this means up to 10^10 operations — far too slow for typical time limits (10^7-10^8 operations per second).

The core inefficiency is redundant boundary scanning. When bar i expands rightward and stops at bar j (because heights[j] < heights[i]), we learn nothing about bar i+1's boundaries — we scan the same region again from scratch. Many bars share the same boundaries, and the brute force rediscovers them independently.

Key insight: For each bar, the rectangle it constrains is bounded by the nearest shorter bar on the left and the nearest shorter bar on the right. If we could find these two boundaries for every bar in O(1), the total work drops to O(n). A monotonic stack achieves exactly this: it maintains bars in increasing height order, so when a shorter bar arrives, it instantly identifies which taller bars are now bounded on the right.

Optimal Approach - Monotonic Stack

Intuition

Instead of expanding from each bar (which rescans neighbors repeatedly), we flip the perspective: we process bars left to right and use a stack to remember bars that haven't yet found their right boundary.

Think of it like a line of people of different heights standing side by side. We scan from left to right. We maintain a stack of people in increasing height order. When a shorter person appears, every taller person still in the stack now knows their right boundary — this shorter person is the first one who blocks them from extending further.

When we pop a taller bar from the stack:

  • The right boundary is the current index (the shorter bar that triggered the pop)
  • The left boundary is the new stack top after popping (the next shorter bar to the left, since the stack maintains increasing order)
  • The width is right_boundary - left_boundary - 1
  • The area is popped_height × width

This way, each bar is pushed once and popped once, giving exactly O(n) total work. The stack acts as a memory of unresolved bars awaiting their right boundary.

Step-by-Step Explanation

Let's trace through heights = [2, 1, 5, 6, 2, 3] using a monotonic stack:

Step 1: Process bar 0 (h=2). Stack is empty → push 0. Stack = [0].

Step 2: Process bar 1 (h=1). h=1 < h[0]=2 → bar 0 cannot extend right past here. Pop 0.

Step 3: Popped bar 0 (h=2). Stack is empty after pop → left boundary is -1. Width = 1 - (-1) - 1 = 1. Area = 2 × 1 = 2. max = 2. Push 1. Stack = [1].

Step 4: Process bar 2 (h=5). h=5 > h[1]=1 → increasing order, push 2. Stack = [1, 2].

Step 5: Process bar 3 (h=6). h=6 > h[2]=5 → increasing order, push 3. Stack = [1, 2, 3].

Step 6: Process bar 4 (h=2). h=2 < h[3]=6 → pop 3. Right = 4, left = stack top = 2. Width = 4 - 2 - 1 = 1. Area = 6 × 1 = 6. max = 6.

Step 7: Still h=2 < h[2]=5 → pop 2. Right = 4, left = stack top = 1. Width = 4 - 1 - 1 = 2. Area = 5 × 2 = 10. max = 10.

Step 8: h=2 > h[1]=1 → stop popping. Push 4. Stack = [1, 4].

Step 9: Process bar 5 (h=3). h=3 > h[4]=2 → push 5. Stack = [1, 4, 5].

Step 10: All bars processed. Pop remaining bars from stack.

Step 11: Pop 5 (h=3). Right = 6 (n), left = 4. Width = 6 - 4 - 1 = 1. Area = 3. max still 10.

Step 12: Pop 4 (h=2). Right = 6, left = 1. Width = 6 - 1 - 1 = 4. Area = 8. max still 10.

Step 13: Pop 1 (h=1). Right = 6, stack empty → left = -1. Width = 6 - (-1) - 1 = 6. Area = 6. max still 10.

Result: max_area = 10.

Monotonic Stack — Finding Boundaries in O(n) — Watch how the monotonic stack maintains bars in increasing height order. When a shorter bar arrives, taller bars are popped and their rectangle area is computed using the stack for boundary information.

Algorithm

  1. Initialize an empty stack and max_area = 0
  2. For each index i from 0 to n-1:
    a. While the stack is not empty AND heights[stack.top()] ≥ heights[i]:
    • Pop the top index. Let h = heights[popped]
    • Compute width: if stack is empty, width = i; else width = i - stack.top() - 1
    • Update max_area = max(max_area, h × width)
      b. Push i onto the stack
  3. After processing all bars, pop remaining entries from the stack:
    a. For each popped index with height h:
    • Compute width: if stack is empty, width = n; else width = n - stack.top() - 1
    • Update max_area = max(max_area, h × width)
  4. Return max_area

Code

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int n = heights.size();
        stack<int> st;
        int maxArea = 0;
        
        for (int i = 0; i < n; i++) {
            // Pop taller bars — they found their right boundary
            while (!st.empty() && heights[st.top()] >= heights[i]) {
                int h = heights[st.top()];
                st.pop();
                int width = st.empty() ? i : i - st.top() - 1;
                maxArea = max(maxArea, h * width);
            }
            st.push(i);
        }
        
        // Drain remaining bars (no shorter bar to their right)
        while (!st.empty()) {
            int h = heights[st.top()];
            st.pop();
            int width = st.empty() ? n : n - st.top() - 1;
            maxArea = max(maxArea, h * width);
        }
        
        return maxArea;
    }
};
class Solution:
    def largestRectangleArea(self, heights: list[int]) -> int:
        n = len(heights)
        stack = []
        max_area = 0
        
        for i in range(n):
            # Pop taller bars — they found their right boundary
            while stack and heights[stack[-1]] >= heights[i]:
                h = heights[stack.pop()]
                width = i if not stack else i - stack[-1] - 1
                max_area = max(max_area, h * width)
            stack.append(i)
        
        # Drain remaining bars
        while stack:
            h = heights[stack.pop()]
            width = n if not stack else n - stack[-1] - 1
            max_area = max(max_area, h * width)
        
        return max_area
class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        Stack<Integer> st = new Stack<>();
        int maxArea = 0;
        
        for (int i = 0; i < n; i++) {
            // Pop taller bars — they found their right boundary
            while (!st.isEmpty() && heights[st.peek()] >= heights[i]) {
                int h = heights[st.pop()];
                int width = st.isEmpty() ? i : i - st.peek() - 1;
                maxArea = Math.max(maxArea, h * width);
            }
            st.push(i);
        }
        
        // Drain remaining bars
        while (!st.isEmpty()) {
            int h = heights[st.pop()];
            int width = st.isEmpty() ? n : n - st.peek() - 1;
            maxArea = Math.max(maxArea, h * width);
        }
        
        return maxArea;
    }
}

Complexity Analysis

Time Complexity: O(n)

Each of the n bar indices is pushed onto the stack exactly once and popped at most once. The total number of push operations is n, and the total number of pop operations is at most n. Every operation inside the while loop (comparison, pop, area calculation) is O(1). Therefore, the total work across all iterations of the outer for-loop is O(n).

Space Complexity: O(n)

In the worst case (heights in strictly increasing order), all n indices are on the stack simultaneously before any pops occur. The stack therefore uses O(n) space.