Largest Rectangle in Histogram Using Stack in DSA Java - Execution Trace

Concept Flow - Largest Rectangle in Histogram Using Stack

Start with empty stack

↓

Iterate over bars

↓

If stack empty or current bar taller

↓

Push index

↓

Calculate area with popped bar

↓

Update max area

↓

Repeat until all bars processed

↓

Pop remaining bars and calculate areas

↓

Return max area

We scan bars left to right, pushing indices of increasing heights. When a lower bar appears, we pop from stack to calculate areas with popped bars as smallest height, updating max area.

Execution Sample

DSA Java

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 h = heights[stack.pop()];
      int w = stack.isEmpty() ? i : i - stack.peek() - 1;
      maxArea = Math.max(maxArea, h * w);
    }
  }
  while (!stack.isEmpty()) {
    int h = heights[stack.pop()];
    int w = stack.isEmpty() ? i : i - stack.peek() - 1;
    maxArea = Math.max(maxArea, h * w);
  }
  return maxArea;
}

Calculates largest rectangle area in histogram by using a stack to track indices of bars with increasing height.

Execution Table

Step	Operation	Current Index i	Stack Content (indices)	Action	Max Area	Visual State (Bars with indices)
1	Start	0	[]	Stack empty, push 0	0	[2(0)]
2	Process bar 1	1	[0]	2 >= 2? Yes, push 1	0	[2(0),1(1)]
3	Process bar 5	2	[0,1]	5 >= 1? Yes, push 2	0	[2(0),1(1),5(2)]
4	Process bar 6	3	[0,1,2]	6 >= 5? Yes, push 3	0	[2(0),1(1),5(2),6(3)]
5	Process bar 2	4	[0,1,2,3]	2 < 6? Pop 3	6	[2(0),1(1),5(2)]
6	Calculate area	4	[0,1,2]	Height=6, Width=1, Area=6	6	[2(0),1(1),5(2)]
7	Process bar 2	4	[0,1,2]	2 < 5? Pop 2	10	[2(0),1(1)]
8	Calculate area	4	[0,1]	Height=5, Width=2, Area=10	10	[2(0),1(1)]
9	Process bar 2	4	[0,1]	2 < 1? No, push 4	10	[2(0),1(1),2(4)]
10	Process bar 3	5	[0,1,4]	3 >= 2? Yes, push 5	10	[2(0),1(1),2(4),3(5)]
11	Process bar 1	6	[0,1,4,5]	1 < 3? Pop 5	10	[0,1,4]
12	Calculate area	6	[0,1,4]	Height=3, Width=1, Area=3	10	[0,1,4]
13	Process bar 1	6	[0,1,4]	1 < 2? Pop 4	10	[0,1]
14	Calculate area	6	[0,1]	Height=2, Width=4, Area=8	10	[0,1]
15	Process bar 1	6	[0,1]	1 < 1? No, push 6	10	[2(0),1(1),1(6)]
16	End of array	7	[0,1,6]	Pop remaining 6	10	[2(0),1(1)]
17	Calculate area	7	[0,1]	Height=1, Width=1, Area=1	10	[2(0),1(1)]
18	Pop remaining 1	7	[0]	Height=1, Width=6, Area=6	10	[2(0)]
19	Pop remaining 2	7	[]	Height=2, Width=7, Area=14	14	[]
20	Return	7	[]	Max area found	14	Final max area = 14

💡 All bars processed and stack emptied, max area is 14

Variable Tracker

Variable	Start	After Step 1	After Step 5	After Step 9	After Step 15	After Step 19	Final
i	0	1	4	6	7	7	7
stack	[]	[0]	[0,1,2]	[0,1,4]	[0,1,6]	[]	[]
maxArea	0	0	10	10	10	14	14

Key Moments - 3 Insights

Why do we pop from the stack when the current bar is lower than the top of the stack?

Because the current lower bar means the previous taller bars can't extend further. We calculate area with popped bar as smallest height (see steps 5-8 in execution_table).

How is the width calculated when popping from the stack?

Width is current index i minus the index now on top of the stack minus one. If stack is empty, width is i (see steps 6 and 7).

Why do we pop remaining bars after processing all histogram bars?

Remaining bars in stack mean they extend to the end. We calculate areas for them considering width up to the end (see steps 16-19).

Visual Quiz - 3 Questions

Look at the execution_table at step 7. What is the maxArea after popping index 2?

A 6

B 10

C 8

D 14

💡 Hint

Check the 'Max Area' column at step 7 in execution_table.

At which step does the stack become empty for the first time?

A Step 19

B Step 9

C Step 1

D Step 16

💡 Hint

Look at the 'Stack Content' column to find when it changes to [].

If the histogram had all bars of equal height, how would the stack behave during iteration?

A Stack would keep all indices until the end

B Stack would pop every time a new bar is processed

C Stack would be empty after first bar

D Stack would alternate push and pop every step

💡 Hint

Refer to the condition for pushing indices in the code and how equal heights affect it.

Concept Snapshot

Largest Rectangle in Histogram Using Stack:
- Use a stack to store indices of bars in increasing height order.
- Push index if current bar >= bar at stack top.
- If current bar < bar at stack top, pop and calculate area.
- Width = current index - stack top index - 1 (or current index if stack empty).
- After processing all bars, pop remaining stack bars to calculate areas.
- Max area updated during each pop.

Full Transcript

This concept finds the largest rectangle area in a histogram using a stack. We scan bars from left to right. We push indices of bars if the current bar is taller or equal to the bar at the top of the stack. When we find a bar shorter than the top of the stack, we pop from the stack and calculate the area with the popped bar as the smallest height. The width is calculated based on the current index and the new top of the stack. We update the maximum area found so far. After processing all bars, we pop any remaining bars in the stack and calculate areas similarly. The maximum area found is returned. The execution table shows step-by-step how the stack changes, when bars are pushed or popped, and how the max area updates. The variable tracker shows how the index, stack content, and max area change over time. Key moments clarify why popping happens, how width is calculated, and why we pop remaining bars at the end. The visual quiz tests understanding of max area updates, stack emptiness, and stack behavior with equal height bars.

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