Largest Rectangle In Histogram

Problem Statement

Given an array heights[] representing the height of histogram bars, find the area of the largest rectangle that can be formed.

Each bar has:

Width = 1

Enter fullscreen mode Exit fullscreen mode

Brute Force Intuition

In an interview, you can explain it like this:

Consider every bar as the smallest bar in a rectangle. Expand towards both left and right until a smaller bar is encountered, then compute the area.

Although straightforward, every expansion scans multiple bars repeatedly.

Complexity

• Time Complexity: O(N²)
• Space Complexity: O(1)

Brute Force Code

class Solution {

    public int largestRectangleArea(int[] heights) {

        int maxArea = 0;

        for (int i = 0; i < heights.length; i++) {

            int minHeight = heights[i];

            for (int j = i; j < heights.length; j++) {

                minHeight = Math.min(minHeight, heights[j]);

                int area = minHeight * (j - i + 1);

                maxArea = Math.max(maxArea, area);
            }
        }

        return maxArea;
    }
}

Enter fullscreen mode Exit fullscreen mode

Moving Towards the Optimal Approach

Instead of expanding for every bar:

Ask:

For every bar,

How far can it expand
towards Left and Right
before finding a smaller bar?

Enter fullscreen mode Exit fullscreen mode

If we know:

• Previous Smaller Element
• Next Smaller Element

then we immediately know the rectangle width.

Pattern Recognition

Whenever you see:

• Nearest Smaller
• Largest Rectangle
• Expansion until Smaller Element

Think:

Monotonic Stack

Key Observation

For every bar:

Area

=

Height

×

Width

Enter fullscreen mode Exit fullscreen mode

Width becomes:

Next Smaller Index

-

Previous Smaller Index

-

1

Enter fullscreen mode Exit fullscreen mode

So we only need to compute:

Previous Smaller

Next Smaller

Enter fullscreen mode Exit fullscreen mode

using Monotonic Stack.

Optimal Approach

Step 1

Find:

Previous Smaller Index

Enter fullscreen mode Exit fullscreen mode

for every element.

Step 2

Find:

Next Smaller Index

Enter fullscreen mode Exit fullscreen mode

for every element.

Step 3

For every index:

width = right[i] - left[i] - 1;

area = heights[i] * width;

Enter fullscreen mode Exit fullscreen mode

Take maximum.

Optimal Java Solution

class Solution {

    public int largestRectangleArea(int[] heights) {

        int n = heights.length;

        int[] left = previousSmaller(heights);

        int[] right = nextSmaller(heights);

        int maxArea = 0;

        for (int i = 0; i < n; i++) {

            int width = right[i] - left[i] - 1;

            int area = heights[i] * width;

            maxArea = Math.max(maxArea, area);
        }

        return maxArea;
    }

    private int[] previousSmaller(int[] arr) {

        int n = arr.length;

        int[] ans = new int[n];

        Stack<Integer> st = new Stack<>();

        for (int i = 0; i < n; i++) {

            while (!st.isEmpty() &&
                   arr[st.peek()] >= arr[i]) {

                st.pop();
            }

            ans[i] = st.isEmpty()
                    ? -1
                    : st.peek();

            st.push(i);
        }

        return ans;
    }

    private int[] nextSmaller(int[] arr) {

        int n = arr.length;

        int[] ans = new int[n];

        Stack<Integer> st = new Stack<>();

        for (int i = n - 1; i >= 0; i--) {

            while (!st.isEmpty() &&
                   arr[st.peek()] >= arr[i]) {

                st.pop();
            }

            ans[i] = st.isEmpty()
                    ? n
                    : st.peek();

            st.push(i);
        }

        return ans;
    }
}

Enter fullscreen mode Exit fullscreen mode

Dry Run

Input

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

Enter fullscreen mode Exit fullscreen mode

Previous Smaller

Index

0 → -1

1 → -1

2 → 1

3 → 2

4 → 1

5 → 4

Enter fullscreen mode Exit fullscreen mode

Next Smaller

Index

0 → 1

1 → 6

2 → 4

3 → 4

4 → 6

5 → 6

Enter fullscreen mode Exit fullscreen mode

Area Calculation

For:

Height = 5

Enter fullscreen mode Exit fullscreen mode

Width:

4 - 1 - 1

= 2

Enter fullscreen mode Exit fullscreen mode

Area:

5 × 2 = 10

Enter fullscreen mode Exit fullscreen mode

Largest Area:

10

Enter fullscreen mode Exit fullscreen mode

Why Monotonic Stack Works?

Each bar is:

Pushed once

Popped once

Enter fullscreen mode Exit fullscreen mode

Hence every index is processed only once.

The stack efficiently finds:

Nearest Smaller Element

Enter fullscreen mode Exit fullscreen mode

on both sides.

Complexity Analysis

Metric Complexity Time Complexity O(N) Space Complexity O(N)

Interview One-Liner

Compute the previous and next smaller element for every bar using a monotonic increasing stack, then calculate the maximum rectangle using height × width.

Pattern Learned

Largest Rectangle

↓

Need Expansion

↓

Nearest Smaller Elements

↓

Monotonic Stack

Enter fullscreen mode Exit fullscreen mode

Similar Problems

• Largest Rectangle in Histogram
• Maximal Rectangle
• Next Smaller Element
• Previous Smaller Element
• Sum of Subarray Minimums

Memory Trick

Think:

Current Bar

↓

Previous Smaller

↓

Next Smaller

↓

Width

↓

Area

Enter fullscreen mode Exit fullscreen mode

Mental Model

Area

=

Height

×

Width

Width

=

Next Smaller

-

Previous Smaller

-

1

Enter fullscreen mode Exit fullscreen mode

Whenever you hear:

“Largest Rectangle in Histogram”

your brain should immediately think:

Previous Smaller + Next Smaller + Monotonic Stack