Jaspreet singh

Posted on Jun 27

Largest Rectangle In Histogram

#algorithms #interview #java #leetcode

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

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;
    }
}

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?

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

Width becomes:

Next Smaller Index

-

Previous Smaller Index

-

1

So we only need to compute:

Previous Smaller

Next Smaller

using Monotonic Stack.

Optimal Approach

Step 1

Find:

Previous Smaller Index

for every element.

Step 2

Find:

Next Smaller Index

for every element.

Step 3

For every index:

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

area = heights[i] * width;

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;
    }
}

Dry Run

Input

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

Previous Smaller

Index

0 → -1

1 → -1

2 → 1

3 → 2

4 → 1

5 → 4

Next Smaller

Index

0 → 1

1 → 6

2 → 4

3 → 4

4 → 6

5 → 6

Area Calculation

For:

Height = 5

Width:

4 - 1 - 1

= 2

Area:

5 × 2 = 10

Largest Area:

Why Monotonic Stack Works?

Each bar is:

Pushed once

Popped once

Hence every index is processed only once.

The stack efficiently finds:

Nearest Smaller Element

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

Memory Trick