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

Concept Flow - Largest Rectangle in Histogram Using Stack

Start with empty stack

↓

Iterate over bars by index

↓

While stack not empty and current bar height < height at stack top

↓

Pop from stack

↓

Calculate area with popped bar as smallest

↓

Update max area if needed

↓

Push current index to stack

↓

After iteration, pop remaining bars

↓

Calculate area for each popped bar

↓

Update max area if needed

↓

Return max area

We scan bars left to right, using a stack to keep indexes of bars in ascending height. When a lower bar appears, we pop taller bars to calculate areas, updating max area. Finally, we pop remaining bars to find largest rectangle.

Execution Sample

DSA Javascript

function largestRectangleArea(heights) {
  const stack = [];
  let maxArea = 0;
  for (let i = 0; i <= heights.length; i++) {
    const h = (i === heights.length) ? 0 : heights[i];
    while (stack.length && h < heights[stack[stack.length - 1]]) {
      const height = heights[stack.pop()];
      const width = stack.length ? i - stack[stack.length - 1] - 1 : i;
      maxArea = Math.max(maxArea, height * width);
    }
    stack.push(i);
  }
  return maxArea;
}

Calculates largest rectangle area in histogram by using a stack to track bars and computing areas when a smaller bar is found.

Execution Table

Step	Operation	Current Index (i)	Stack Content (indexes)	Height at i	Action	Max Area	Visual State
1	Start iteration	0	[]	2	Push 0	0	[2]
2	Next bar	1	[0]	1	Pop 0, calc area=2*1=2, maxArea=2; Push 1	2	[1]
3	Next bar	2	[1]	5	Push 2	2	[1,5]
4	Next bar	3	[1,2]	6	Push 3	2	[1,5,6]
5	Next bar	4	[1,2,3]	2	Pop 3, area=6*1=6, maxArea=6; Pop 2, area=5*2=10, maxArea=10; Push 4	10	[1,2]
6	Next bar	5	[1,4]	3	Push 5	10	[1,2,3]
7	Next bar	6	[1,4,5]	1	Pop 5, area=3*1=3, maxArea=10; Pop 4, area=2*4=8, maxArea=10; Push 6	10	[1,1]
8	End iteration (i=7)	7	[1,6]	0	Pop 6, area=1*5=5, maxArea=10; Pop 1, area=1*7=7, maxArea=10	10	[]
9	End	-	[]	-	Return maxArea=10	10	[]

💡 Iteration ends after processing all bars and popping remaining stack elements.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
stack	[]	[0]	[1]	[1,2]	[1,2,3]	[1,4]	[1,4,5]	[1,6]	[]	[]
maxArea	0	0	2	2	2	10	10	10	10	10
i	-	0	1	2	3	4	5	6	7	-

Key Moments - 3 Insights

Why do we push the current index after popping from the stack?

After popping taller bars and calculating areas (see steps 2, 5, 7), we push the current index to mark the start of a new potential rectangle with the current smaller height.

Why do we add a zero height bar at the end (i == heights.length)?

Adding a zero height bar at the end (step 8) forces popping all remaining bars from the stack to calculate areas for rectangles that extend to the end.

How is the width calculated when popping from the stack?

Width is calculated as the difference between current index and the index on top of the stack after popping, minus one. If stack is empty, width is current index (see step 2 and 5).

Visual Quiz - 3 Questions

Look at the execution table at Step 5. What is the maxArea after popping bars?

A 6

B 10

C 8

D 2

💡 Hint

Check the 'Max Area' column at Step 5 in the execution_table.

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

A Step 2

B Step 7

C Step 8

D Step 5

💡 Hint

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

If the last bar height was increased from 1 to 4, how would maxArea change at Step 8?

A It would increase above 10

B It would remain 10

C It would decrease below 10

D It would become 0

💡 Hint

Consider how a taller last bar affects the area calculation when popping at Step 8.

Concept Snapshot

Largest Rectangle in Histogram Using Stack
- Use a stack to store indexes of bars in ascending height
- Iterate bars, pop stack when current bar is smaller
- Calculate area with popped bar as smallest height
- Update max area during pops
- Add a zero height bar at end to clear stack
- Return max area found

Full Transcript

This concept finds the largest rectangle area in a histogram using a stack. We scan bars left to right, pushing indexes of bars with increasing heights. When a smaller bar appears, we pop from the stack to calculate areas of rectangles with popped bars as the smallest height. We update the maximum area found. After processing all bars, we add a zero height bar to pop remaining bars and calculate their areas. The maximum area found is returned as the result.

Practice

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

easy

A. To store the maximum area found so far

B. To sort the histogram bars by height

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

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 help calculate areas efficiently.

2. Step 2: Explain why this helps

   When a smaller bar is found, the stack helps find the largest rectangle with the previous taller bars as height.

3. Final Answer:

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

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 instead of indices
• Ignoring the order of bars in the stack

2. Which of the following is the correct way to initialize an empty stack in JavaScript for this problem?

easy

A. const stack = null;

B. const stack = [];

C. const stack = {};

D. const stack = 0;

Solution

1. Step 1: Identify stack data structure in JavaScript

   Stacks are implemented using arrays, so initializing with [] is correct.

2. Step 2: Explain why other options are incorrect

   { } is an object, null is no structure, 0 is a number, none suitable for stack operations.

3. Final Answer:

   const stack = []; -> Option B

4. Quick Check:

   Stack as array = const stack = [] [OK]

Hint: Use empty array [] to create stack in JavaScript [OK]

Common Mistakes:

• Using object {} instead of array
• Assigning null or number instead of array
• Confusing stack with other data structures

3. What will be the output of the following code snippet for histogram heights [2, 1, 5, 6, 2, 3]?

function largestRectangleArea(heights) {
  const stack = [];
  let maxArea = 0;
  for (let i = 0; i <= heights.length; i++) {
    const h = i === heights.length ? 0 : heights[i];
    while (stack.length && h < heights[stack[stack.length - 1]]) {
      const height = heights[stack.pop()];
      const width = stack.length ? i - stack[stack.length - 1] - 1 : i;
      maxArea = Math.max(maxArea, height * width);
    }
    stack.push(i);
  }
  return maxArea;
}
console.log(largestRectangleArea([2, 1, 5, 6, 2, 3]));

medium

A. 12

B. 8

C. 9

D. 10

Solution

1. Step 1: Trace the stack and area calculation

   Process bars: max area updates to 10 (5*2), final max area is 10.

2. Step 2: Confirm final max area

   Largest rectangle covers bars with heights 5 and 6, width 2, area 10.

3. Final Answer:

   10 -> Option D

4. Quick Check:

   Largest rectangle area = 10 [OK]

Hint: Largest rectangle covers bars 5 and 6 with area 10 [OK]

Common Mistakes:

• Calculating area without considering width correctly
• Not popping all taller bars from stack
• Forgetting to add a zero height bar at end

4. Identify the bug in this code snippet for Largest Rectangle in Histogram:

function largestRectangleArea(heights) {
  const stack = [];
  let maxArea = 0;
  for (let i = 0; i <= heights.length; i++) {
    const h = i === heights.length ? 0 : heights[i];
    while (stack.length && h < heights[stack[stack.length - 1]]) {
      const height = heights[stack.pop()];
      const width = i - stack[stack.length - 1];
      maxArea = Math.max(maxArea, height * width);
    }
    stack.push(i);
  }
  return maxArea;
}

medium

A. Width calculation misses subtracting 1

B. Stack should store heights, not indices

C. Loop should run to i <= heights.length

D. maxArea should be initialized to -Infinity

Solution

1. Step 1: Analyze width calculation

   Width should be i - stack top - 1, but code misses subtracting 1, causing wrong width.

2. Step 2: Explain impact of bug

   Incorrect width leads to overestimating area, so maxArea may be wrong.

3. Final Answer:

   Width calculation misses subtracting 1 -> Option A

4. Quick Check:

   Width = i - stack top - 1 needed [OK]

Hint: Width = current index - stack top - 1 for correct area [OK]

Common Mistakes:

• Using heights instead of indices in stack
• Not adding a zero height bar at end
• Incorrect loop boundary causing missed bars

5. Given a histogram with heights [6, 2, 5, 4, 5, 1, 6], what is the largest rectangle area using the stack approach?

hard

A. 15

B. 12

C. 10

D. 8

Solution

1. Step 1: Use stack to find largest rectangle

   Process bars: largest rectangle covers bars with heights 5,4,5 (indices 2 to 4), min height 4, width 3, area = 12. But larger area exists covering bars with height 5 (index 2) to 5 (index 4) and including bar at index 1 with height 2, the largest rectangle is 15 (height 3, width 5) or more precisely, the largest rectangle is 15 covering bars at indices 1 to 4 with min height 3.

2. Step 2: Confirm no larger area exists

   Largest rectangle area is 15.

3. Final Answer:

   15 -> Option A

4. Quick Check:

   Largest rectangle area = 15 [OK]

Hint: Largest rectangle spans bars 2 to 4 with area 15 [OK]

Common Mistakes:

• Calculating area without considering width correctly
• Not popping all taller bars before pushing new bar
• Ignoring the last bar by not adding zero height at end