Largest Rectangle in Histogram Using Stack in DSA Typescript

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 calculate the biggest flat area you can make with those books.

Histogram bars: heights = [2, 1, 5, 6, 2, 3]
Stack stores indices of bars in increasing height order.

Initial:
Index: 0  1  2  3  4  5
Height:2  1  5  6  2  3
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) onto stack

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

Why: Start with first bar, stack keeps indices of increasing heights

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

Popped index 0 (height 2), stack now empty
Calculate area: height 2 * width 1 = 2
Push index 1 (height 1)

Why: Found a smaller bar, so calculate area for taller bars before it

Step 3: Push index 2 (height 5) onto stack

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

Why: Height 5 is greater than height at stack top (1), so push

Step 4: Push index 3 (height 6) onto stack

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

Why: Height 6 is greater than height at stack top (5), so push

Step 5: Current bar height 2 is less than height at stack top (6), pop index 3 and calculate area

Popped index 3 (height 6), stack: [1, 2]
Area: height 6 * width 1 = 6

Why: Smaller bar found, calculate area for taller bar

Step 6: Current bar height 2 is less than height at stack top (5), pop index 2 and calculate area

Popped index 2 (height 5), stack: [1]
Area: height 5 * width 2 = 10

Why: Calculate area for bar 5 spanning indices 2 to 3

Step 7: Push index 4 (height 2) onto stack

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

Why: Height 2 is greater than height at stack top (1), so push

Step 8: Push index 5 (height 3) onto stack

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

Why: Height 3 is greater than height at stack top (2), so push

Step 9: Reached end, pop remaining bars and calculate areas

Pop index 5 (height 3), area = 3 * 1 = 3
Pop index 4 (height 2), area = 2 * 4 = 8
Pop index 1 (height 1), area = 1 * 6 = 6

Why: Calculate areas for remaining bars to find max

Result:

Largest rectangle area = 10
Final stack empty

Annotated Code

DSA Typescript

class LargestRectangleHistogram {
  static largestRectangleArea(heights: number[]): number {
    const stack: number[] = [];
    let maxArea = 0;
    let i = 0;
    while (i < heights.length) {
      if (stack.length === 0 || heights[i] >= heights[stack[stack.length - 1]]) {
        stack.push(i); // push index of current bar
        i++;
      } else {
        const top = stack.pop()!; // pop top
        const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1; // calculate width
        const area = heights[top] * width; // calculate area
        if (area > maxArea) maxArea = area; // update max
      }
    }
    while (stack.length > 0) {
      const top = stack.pop()!; // pop remaining bars
      const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1; // width
      const area = heights[top] * width; // area
      if (area > maxArea) maxArea = area; // update max
    }
    return maxArea;
  }
}

// Driver code
const histogram = [2, 1, 5, 6, 2, 3];
const result = LargestRectangleHistogram.largestRectangleArea(histogram);
console.log(result);

if (stack.length === 0 || heights[i] >= heights[stack[stack.length - 1]]) {

push current index if stack empty or current height >= height at stack top

stack.push(i);

store index of current bar to track increasing heights

const top = stack.pop()!;

pop top index to calculate area for that bar

const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;

calculate width of rectangle using current index and new stack top

const area = heights[top] * width;

calculate area for popped bar

if (area > maxArea) maxArea = area;

update max area if current area is larger

while (stack.length > 0) {

after processing all bars, pop remaining bars to calculate areas

Output

10

Complexity Analysis

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

Space: O(n) for the stack storing indices of bars

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

Edge Cases

empty histogram

returns 0 as no bars exist

DSA Typescript

while (i < heights.length) {

all bars same height

calculates area as height * number of bars

DSA Typescript

if (stack.length === 0 || heights[i] >= heights[stack[stack.length - 1]]) {

strictly increasing heights

pushes all bars, then calculates area at end

DSA Typescript

while (stack.length > 0) {

When to Use This Pattern

When asked for largest rectangle area in a histogram, use a stack 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 top index - 1 or current index if stack empty

Mistake: Pushing indices without checking height order
Fix: Only push if current height >= height at stack top to maintain increasing order

Summary

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

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

The key is to keep indices of bars in increasing height order and 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 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