Why Largest Rectangle in Histogram Using Stack in DSA Typescript?

The Big Idea

Discover how a simple stack can turn a slow, tiring problem into a quick and clever solution!

The Scenario

Imagine you have a row of buildings with different heights, and you want to find the largest flat area you can cover by choosing some consecutive buildings. Doing this by checking every possible group of buildings one by one is like measuring every possible rectangle by hand.

The Problem

Manually checking every group of buildings is very slow and tiring. It takes a lot of time because you have to look at many combinations, and it's easy to make mistakes counting or missing some groups.

The Solution

Using a stack helps keep track of building heights in a smart way. It lets you quickly find the biggest rectangle by remembering where heights start and end, so you don't have to check every group manually. This makes the process fast and simple.

Before vs After

✗ Before

function largestRectangleArea(heights: number[]): number {
  let maxArea = 0;
  for (let i = 0; i < heights.length; i++) {
    for (let j = i; j < heights.length; j++) {
      let minHeight = Math.min(...heights.slice(i, j + 1));
      maxArea = Math.max(maxArea, minHeight * (j - i + 1));
    }
  }
  return maxArea;
}

✓ After

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);
    }
    stack.push(i);
  }
  return maxArea;
}

What It Enables

This method lets you quickly find the largest rectangle in a histogram, making it easy to solve problems about areas and heights efficiently.

Real Life Example

Think about packing boxes of different heights on a shelf and wanting to find the biggest flat space to place a new box. This method helps find that space fast.

Key Takeaways

Manual checking of all groups is slow and error-prone.

Stack helps track heights and widths smartly for fast calculation.

Enables quick finding of largest rectangle in a histogram.

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