Largest Rectangle in Histogram Using Stack in DSA Java

Mental Model

We use a stack to keep track of bars in increasing height order to find the largest rectangle efficiently.

Analogy: Imagine stacking books by height on a shelf. When a shorter book comes, you remove taller books to measure the largest flat space you can get between them.

Histogram bars: heights = [2, 1, 5, 6, 2, 3]
Index:       0  1  2  3  4  5
Bars:       2 -> 1 -> 5 -> 6 -> 2 -> 3
Stack: empty initially
We push indices of bars with increasing heights to stack.

Dry Run Walkthrough

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

Goal: Find the largest rectangle area that can be formed in the histogram

Step 1: Push index 0 (height 2) to stack

Stack: [0]
Histogram: 2 -> 1 -> 5 -> 6 -> 2 -> 3

Why: Start with first bar, stack keeps indices of bars in increasing height

Step 2: Current bar height 1 < height at stack top (2), pop index 0 and calculate area

Pop 0: height=2, width=1 (since stack empty), area=2*1=2
Stack: []

Why: Found smaller bar, so calculate area with taller bar before it

Step 3: Push index 1 (height 1) to stack

Stack: [1]
Histogram: 2 -> 1 -> 5 -> 6 -> 2 -> 3

Why: Stack empty, push current index

Step 4: Push index 2 (height 5) to stack

Stack: [1, 2]
Histogram: 2 -> 1 -> 5 -> 6 -> 2 -> 3

Why: Current height 5 > height at stack top 1, keep increasing order

Step 5: Push index 3 (height 6) to stack

Stack: [1, 2, 3]
Histogram: 2 -> 1 -> 5 -> 6 -> 2 -> 3

Why: Current height 6 > height at stack top 5, keep increasing order

Step 6: Current bar height 2 < height at stack top (6), pop index 3 and calculate area

Pop 3: height=6, width=1 (4 - 2 - 1), area=6*1=6
Stack: [1, 2]

Why: Smaller bar found, calculate area with taller bar

Step 7: Current bar height 2 < height at stack top (5), pop index 2 and calculate area

Pop 2: height=5, width=2 (index 4 - index 1 - 1), area=5*2=10
Stack: [1]

Why: Keep popping taller bars to find max area

Step 8: Push index 4 (height 2) to stack

Stack: [1, 4]
Histogram: 2 -> 1 -> 5 -> 6 -> 2 -> 3

Why: Current height 2 > height at stack top 1, push index

Step 9: Push index 5 (height 3) to stack

Stack: [1, 4, 5]
Histogram: 2 -> 1 -> 5 -> 6 -> 2 -> 3

Why: Current height 3 > height at stack top 2, push index

Step 10: End of histogram reached, pop remaining bars and calculate areas

Pop 5: height=3, width=1, area=3*1=3
Pop 4: height=2, width=4 (index 6 - index 1 - 1), area=2*4=8
Pop 1: height=1, width=6 (index 6 - empty stack), area=1*6=6
Stack: []

Why: Calculate area for remaining bars to find max

Result:

Largest rectangle area = 10
Final stack empty

Annotated Code

DSA Java

import java.util.Stack;

public class LargestRectangleHistogram {
    public static int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        int i = 0;
        while (i < heights.length) {
            if (stack.isEmpty() || heights[i] >= heights[stack.peek()]) {
                stack.push(i); // push index of current bar
                i++;
            } else {
                int top = stack.pop(); // pop top
                int width = stack.isEmpty() ? i : i - stack.peek() - 1; // calculate width
                int area = heights[top] * width; // calculate area
                if (area > maxArea) maxArea = area; // update max
            }
        }
        while (!stack.isEmpty()) {
            int top = stack.pop();
            int width = stack.isEmpty() ? i : i - stack.peek() - 1;
            int area = heights[top] * width;
            if (area > maxArea) maxArea = area;
        }
        return maxArea;
    }

    public static void main(String[] args) {
        int[] histogram = {2, 1, 5, 6, 2, 3};
        int result = largestRectangleArea(histogram);
        System.out.println("Largest rectangle area = " + result);
    }
}

if (stack.isEmpty() || heights[i] >= heights[stack.peek()]) {

push current index if stack empty or current bar taller or equal to top bar

stack.push(i);

push index of current bar to stack

int top = stack.pop();

pop top index to calculate area with that bar height

int width = stack.isEmpty() ? i : i - stack.peek() - 1;

calculate width of rectangle using current index and stack top

int area = heights[top] * width;

calculate area with popped bar height and width

if (area > maxArea) maxArea = area;

update max area if current area is larger

while (!stack.isEmpty()) {

after processing all bars, pop remaining bars to calculate area

Output

Largest rectangle area = 10

Complexity Analysis

Time: O(n) because each bar is pushed and popped at most once from the stack

Space: O(n) for the stack to store indices in worst case when bars are increasing

vs Alternative: Naive approach checks all pairs and is O(n^2), stack method is much faster with O(n)

Edge Cases

empty histogram

returns 0 as no bars exist

DSA Java

while (i < heights.length) {

all bars same height

largest rectangle is height * number of bars

DSA Java

if (stack.isEmpty() || heights[i] >= heights[stack.peek()]) {

strictly increasing bars

stack grows until end, then pops all to calculate area

DSA Java

while (!stack.isEmpty()) {

When to Use This Pattern

When asked to find largest rectangle area in a histogram or similar structure, use the stack pattern to track increasing heights and calculate areas efficiently.

Common Mistakes

Mistake: Not calculating width correctly when popping from stack
Fix: Use width = current_index - stack.peek() - 1 if stack not empty, else width = current_index

Mistake: Pushing indices without checking height order, causing wrong area calculations
Fix: Only push if current bar height >= height at stack top

Summary

Finds the largest rectangle area in a histogram using a stack to track bars.

Use when you need to efficiently calculate max rectangle area in bar charts or histograms.

The key is to keep indices of bars in increasing height order to calculate areas when a smaller bar appears.

Practice

1. What is the main purpose of using a stack in the Largest Rectangle in Histogram problem?

easy

A. To keep track of bars' indices with increasing heights

B. To sort the histogram bars by height

C. To store the maximum area found so far

D. To reverse the order of histogram bars

Solution

1. Step 1: Understand the role of the stack

   The stack stores indices of bars in increasing height order to efficiently find boundaries for rectangles.

2. Step 2: Why increasing order is important

   When a lower height bar is found, it signals the end of rectangles for taller bars, allowing area calculation.

3. Final Answer:

   To keep track of bars' indices with increasing heights -> Option A

4. Quick Check:

   Stack tracks increasing bars = To keep track of bars' indices with increasing heights [OK]

Hint: Stack stores indices of increasing heights for area calculation [OK]

Common Mistakes:

• Thinking stack sorts bars by height
• Using stack to store areas directly
• Ignoring the order of bars in stack

2. Which of the following Java code snippets correctly initializes an empty stack to store integers for the histogram problem?

easy

A. Stack<Integer> stack = new Stack<int>();

B. Stack stack = new Stack<int>();

C. Stack<int> stack = new Stack<>();

D. Stack<Integer> stack = new Stack<>();

Solution

1. Step 1: Identify correct generic syntax in Java

   Java uses generics with angle brackets and wrapper classes like Integer, not primitive int.

2. Step 2: Check each option

   Stack<Integer> stack = new Stack<>(); uses Stack<Integer> stack = new Stack<>(); which is correct syntax for an empty integer stack.

3. Final Answer:

   Stack<Integer> stack = new Stack<>(); -> Option D

4. Quick Check:

   Correct generic syntax = Stack<Integer> stack = new Stack<>(); [OK]

Hint: Use wrapper class Integer with generics and diamond operator [OK]

Common Mistakes:

• Using primitive int in generics
• Missing diamond operator <>
• Not specifying generic type

3. What is the output of the following Java code snippet that calculates the largest rectangle area in histogram heights = {2, 1, 5, 6, 2, 3}?

public class Histogram {
    public static int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0, i = 0;
        while (i < heights.length) {
            if (stack.isEmpty() || heights[i] >= heights[stack.peek()]) {
                stack.push(i++);
            } else {
                int top = stack.pop();
                int area = heights[top] * (stack.isEmpty() ? i : i - stack.peek() - 1);
                maxArea = Math.max(maxArea, area);
            }
        }
        while (!stack.isEmpty()) {
            int top = stack.pop();
            int area = heights[top] * (stack.isEmpty() ? i : i - stack.peek() - 1);
            maxArea = Math.max(maxArea, area);
        }
        return maxArea;
    }

    public static void main(String[] args) {
        int[] heights = {2, 1, 5, 6, 2, 3};
        System.out.println(largestRectangleArea(heights));
    }
}

medium

A. 12

B. 10

C. 8

D. 6

Solution

1. Step 1: Trace the stack operations and area calculations

   For heights {2,1,5,6,2,3}, the largest rectangle area is 10 (from bars 5 and 6 with width 2).

2. Step 2: Confirm final maxArea value

   After processing all bars and stack cleanup, maxArea is 10.

3. Final Answer:

   10 -> Option B

4. Quick Check:

   Largest rectangle area = 10 [OK]

Hint: Largest area is max of heights[top] * width during stack pops [OK]

Common Mistakes:

• Miscomputing width when stack is empty
• Not popping all remaining bars after loop
• Confusing indices with heights

4. Identify the bug in the following Java method for Largest Rectangle in Histogram and select the fix:

public static int largestRectangleArea(int[] heights) {
    Stack<Integer> stack = new Stack<>();
    int maxArea = 0, i = 0;
    while (i < heights.length) {
        if (stack.isEmpty() || heights[i] > heights[stack.peek()]) {
            stack.push(i++);
        } else {
            int top = stack.pop();
            int area = heights[top] * (stack.isEmpty() ? i : i - stack.peek() - 1);
            maxArea = Math.max(maxArea, area);
        }
    }
    while (!stack.isEmpty()) {
        int top = stack.pop();
        int area = heights[top] * (stack.isEmpty() ? i : i - stack.peek() - 1);
        maxArea = Math.max(maxArea, area);
    }
    return maxArea;
}

medium

A. Initialize maxArea to Integer.MIN_VALUE instead of 0

B. Replace stack with a queue for correct order

C. Change '>' to '>=' in the if condition to handle equal heights

D. Remove the second while loop to avoid double counting

Solution

1. Step 1: Analyze the if condition in the main loop

   The condition uses '>' which skips pushing bars of equal height, causing incorrect area calculation.

2. Step 2: Fix by changing '>' to '>='

   Using '>=' ensures bars of equal height are pushed, maintaining correct stack order and area calculation.

3. Final Answer:

   Change '>' to '>=' in the if condition to handle equal heights -> Option C

4. Quick Check:

   Use '>=' to handle equal heights correctly [OK]

Hint: Use '>=' to push equal height bars to stack [OK]

Common Mistakes:

• Using '>' causes missing equal height bars
• Removing second loop causes incomplete area calculation
• Using queue breaks LIFO needed for stack

5. Given a histogram with heights = {6, 2, 5, 4, 5, 1, 6}, what is the largest rectangle area using the stack approach? Explain how the stack helps find this area.

hard

A. 15

B. 10

C. 12

D. 8

Solution

1. Step 1: Use stack to track indices of increasing heights

   Push indices while heights increase; pop when current height is less, calculating area with popped height as smallest bar.

2. Step 2: Calculate largest area for given heights

   For {6,2,5,4,5,1,6}, largest rectangle area is 15 (bars at indices 0 and 6 with height 6 and width 1, or bars 2,3,4 with height 4 and width 3, but max is 15 from bars 0 to 0 or 6 to 6 or combined area 15 from bars 2,3,4 with height 5 and width 3).

3. Final Answer:

   15 -> Option A

4. Quick Check:

   Stack helps find max area = 15 [OK]

Hint: Stack pops calculate max area using height * width [OK]

Common Mistakes:

• Not popping all bars after iteration
• Incorrect width calculation when stack is empty
• Ignoring bars with same height