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

Concept Flow - Largest Rectangle in Histogram Using Stack

Start with empty stack

↓

Iterate over bars

↓

While current bar < top of stack bar

↓

Pop from stack and calculate area

↓

Update max area if needed

↓

Push current bar index to stack

↓

Repeat until all bars processed

↓

Pop remaining bars and calculate area

↓

Return max area

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

Execution Sample

DSA Typescript

function largestRectangleArea(heights: number[]): number {
  const stack: number[] = [];
  let maxArea = 0;
  for (let i = 0; i <= heights.length; i++) {
    while (stack.length && (i === heights.length || heights[i] < 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);
    }
    if (i < heights.length) {
      stack.push(i);
    }
  }
  return maxArea;
}

// Example: heights = [2,1,5,6,2,3] returns 10

Calculates the largest rectangle area in a 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 Top of Stack	Action	Max Area	Visual State
1	Start	0	[]	N/A	Push 0	0	[2]
2	Next bar	1	[0]	2	Pop 0, Calculate area: height=2, width=1	2	[]
3	After pop	1	[]	N/A	Push 1	2	[1]
4	Next bar	2	[1]	1	Push 2	2	[1,5]
5	Next bar	3	[1,2]	5	Push 3	2	[1,5,6]
6	Next bar	4	[1,2,3]	6	Pop 3, Calculate area: height=6, width=1	6	[1,5]
7	After pop	4	[1,2]	5	Pop 2, Calculate area: height=5, width=2	10	[1]
8	After pop	4	[1]	1	Push 4	10	[1,2]
9	Next bar	5	[1,4]	2	Push 5	10	[1,2,3]
10	End of array	6	[1,4,5]	3	Pop 5, Calculate area: height=3, width=1	10	[1,2]
11	After pop	6	[1,4]	2	Pop 4, Calculate area: height=2, width=4	10	[1]
12	After pop	6	[1]	1	Pop 1, Calculate area: height=1, width=6	10	[]
13	End	6	[]	N/A	Done	10	Final max area = 10

💡 All bars processed and stack emptied, max area found is 10

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	After Step 9	After Step 10	After Step 11	After Step 12	Final
i	0	0	1	1	2	3	4	4	4	5	6	6	6	6
stack	[]	[0]	[]	[1]	[1,2]	[1,2,3]	[1,2]	[1]	[1,4]	[1,4,5]	[1,4]	[1]	[]	[]
maxArea	0	0	2	2	2	2	6	10	10	10	10	10	10	10

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 right. We calculate area for those popped bars using their height and width determined by current index and stack top (see steps 2,6,7,10,11,12 in execution_table).

Why do we push the current index after popping bars?

After popping taller bars, we push the current index to mark the start of a new potential rectangle with this lower height (see steps 3,8). This keeps stack in ascending order of heights.

Why do we run the loop until i <= heights.length instead of i < heights.length?

We run one extra iteration (i == heights.length) to pop and calculate areas for all remaining bars in the stack, ensuring no bars are left unprocessed (see steps 10,11,12 and 13).

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what is the maxArea after popping index 2?

A 2

B 10

C 6

D 0

💡 Hint

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

At which step does the maxArea first become 10?

A Step 6

B Step 8

C Step 7

D Step 12

💡 Hint

Look at the 'Max Area' column in execution_table and find when it updates to 10

At step 4 (i=2), why was there no pop from the stack before pushing 2?

A heights[2] >= heights[1]

B heights[2] < heights[1]

C Stack was empty

D i was at end of array

💡 Hint

heights = [2,1,5,6,2,3], heights[2]=5 > heights[1]=1 (check step 4 stack top)

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 lower
- Calculate area with popped bar height and width
- Update max area during pops
- After iteration, pop remaining bars
- Return max area found

Full Transcript

This visualization shows how to find the largest rectangle in a histogram using a stack. We keep indexes of bars in ascending height order. When a lower bar appears, we pop taller bars from the stack and calculate the area for each popped bar using its height and the width determined by the current index and the new top of the stack. We update the maximum area found so far during these calculations. After processing all bars, we pop any remaining bars to calculate their areas. The largest area found is returned. The execution table traces each step, showing stack content, current index, actions, and max area updates. The variable tracker shows how the index, stack, and max area change over time. Key moments clarify why we pop bars and why we do an extra iteration. The quiz tests understanding of these steps and stack behavior.

Practice

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

easy

A. To reverse the order of histogram bars

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

C. To store the maximum area found so far

D. To sort the histogram bars by height

Solution

1. Step 1: Understand the stack's role

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

2. Step 2: Why increasing heights?

   This helps identify when a bar is lower than the previous, signaling to calculate area for taller bars.

3. Final Answer:

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

4. Quick Check:

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

Hint: Stack holds indices of increasing bars to find rectangle widths [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 TypeScript code snippets correctly initializes an empty stack for indices in the Largest Rectangle problem?

easy

A. const stack = new Stack<number>();

B. const stack: string[] = [];

C. const stack: number[] = [];

D. const stack = []; stack.push('index');

Solution

1. Step 1: Identify correct stack type

   We need a stack of numbers (indices), so number[] is correct.

2. Step 2: Check other options

   const stack: string[] = []; uses string[], wrong type. const stack = new Stack<number>(); uses a Stack class which is not standard in TypeScript. const stack = []; stack.push('index'); pushes a string 'index', wrong type.

3. Final Answer:

   const stack: number[] = []; -> Option C

4. Quick Check:

   Stack of numbers = const stack: number[] = []; [OK]

Hint: Use number[] for stack of indices in TypeScript [OK]

Common Mistakes:

• Using string[] instead of number[]
• Assuming Stack class exists by default
• Pushing wrong data types into stack

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

function largestRectangleArea(heights: number[]): number {
  const stack: number[] = [];
  let maxArea = 0;
  heights.push(0);
  for (let i = 0; i < heights.length; i++) {
    while (stack.length && heights[i] < 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. 10

B. 12

C. 8

D. 6

Solution

1. Step 1: Add sentinel and iterate

   Heights become [2,1,5,6,2,3,0]. We use stack to track indices of increasing bars.

2. Step 2: Calculate max area during pops

   Pop bars when current height is less, calculate area: max area found is 10 (from bars 5 and 6 with width 2).

3. Final Answer:

   10 -> Option A

4. Quick Check:

   Max rectangle area = 10 [OK]

Hint: Add 0 height at end to flush stack and find max area [OK]

Common Mistakes:

• Not adding sentinel 0 at end
• Wrong width calculation after popping
• Ignoring last bars in stack

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

function largestRectangleArea(heights: number[]): number {
  const stack: number[] = [];
  let maxArea = 0;
  for (let i = 0; i <= heights.length; i++) {
    while (stack.length && heights[i] < 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;
}

medium

A. maxArea is not updated inside the loop

B. Stack is not initialized properly

C. Width calculation is incorrect

D. Loop goes out of bounds accessing heights[i] when i == heights.length

Solution

1. Step 1: Check loop boundary

   The loop runs i from 0 to heights.length inclusive, so heights[i] is accessed when i == heights.length, causing out-of-bounds error.

2. Step 2: Fix by adding sentinel or changing loop

   Adding a 0 height at end or changing loop to i < heights.length fixes this.

3. Final Answer:

   Loop goes out of bounds accessing heights[i] when i == heights.length -> Option D

4. Quick Check:

   Out-of-bounds access = Loop goes out of bounds accessing heights[i] when i == heights.length [OK]

Hint: Avoid accessing heights[i] when i equals length without sentinel [OK]

Common Mistakes:

• Ignoring loop boundary causing runtime error
• Assuming stack initialization is wrong
• Misreading width calculation

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

hard

A. 12

B. 10

C. 15

D. 8

Solution

1. Step 1: Use stack to find max area

   Push indices while heights increase. When a lower bar appears, pop and calculate area. For this histogram, max area is 12 from bars at indices 2,3,4 (heights 5,4,5) width 3.

2. Step 2: Why area 12 is largest

   The rectangle covers bars with heights >=4 over width 3, area = 4*3=12. No other rectangle covers more area.

3. Final Answer:

   12 -> Option A

4. Quick Check:

   Max rectangle area = 12 [OK]

Hint: Pop stack on lower bar, calculate area with width between indices [OK]

Common Mistakes:

• Calculating area only for single bars
• Ignoring width when popping multiple bars
• Missing the largest rectangle spanning multiple bars