Largest Rectangle in Histogram Using Stack in DSA Typescript - Deep Dive

Overview - Largest Rectangle in Histogram Using Stack

What is it?

The Largest Rectangle in Histogram problem asks us to find the biggest rectangle that can fit inside a histogram made of bars of different heights. Each bar has a width of 1 unit. We want to find the area of the largest rectangle that can be formed by one or more consecutive bars. This problem helps us understand how to use stacks to solve range and area problems efficiently.

Why it matters

Without this method, finding the largest rectangle would require checking every possible group of bars, which takes a lot of time and is slow for big histograms. Using a stack makes the process much faster and smarter. This is important in real-world tasks like image processing, stock market analysis, or building efficient layouts where we need to quickly find maximum areas or ranges.

Where it fits

Before learning this, you should understand arrays, loops, and the stack data structure basics. After this, you can explore more complex range queries, segment trees, or problems involving monotonic stacks and dynamic programming.

Mental Model

Core Idea

Use a stack to keep track of bars in increasing height order so that when a shorter bar appears, you can calculate the largest rectangle possible with the taller bars before it.

Think of it like...

Imagine stacking books by height on a shelf from shortest to tallest. When you find a book shorter than the last one, you remove taller books one by one to see how much shelf space they cover, finding the biggest space you can use.

Histogram bars: heights = [2, 1, 5, 6, 2, 3]
Stack stores indices of bars with increasing heights

Start -> Stack empty
Push index 0 (height 2)
Next bar height 1 < 2, pop 0 and calculate area
Push index 1
Push index 2 (height 5)
Push index 3 (height 6)
Next bar height 2 < 6, pop 3, calculate area
Pop 2, calculate area
Push index 4
Push index 5
End: pop remaining stack and calculate areas

Stack example:
┌─────┐
│  i  │
├─────┤
│  1  │ height 1
│  4  │ height 2
│  5  │ height 3
└─────┘

Build-Up - 7 Steps

1

Foundation

Understanding Histogram and Rectangle Area

Concept: Introduce what a histogram is and how rectangles form inside it.

A histogram is a set of bars placed side by side, each with a certain height. Each bar has a width of 1 unit. The area of a rectangle formed by consecutive bars is the height of the shortest bar times the number of bars. For example, bars with heights [2, 1, 5] can form rectangles like: - Single bars: area 2, 1, or 5 - Two bars: min height 1 * width 2 = 2 - Three bars: min height 1 * width 3 = 3 We want to find the largest such area.

Result

You understand how to calculate the area of rectangles formed by consecutive bars in a histogram.

Knowing how rectangle areas relate to bar heights and widths is the foundation for solving the largest rectangle problem.

2

Foundation

Basics of Stack Data Structure

Concept: Learn what a stack is and how it works with push and pop operations.

A stack is like a pile of plates: you add plates on top (push) and remove the top plate first (pop). It follows Last-In-First-Out (LIFO) order. Stacks help us remember recent items and process them in reverse order. For example: - Start empty - Push 2, stack: [2] - Push 5, stack: [2, 5] - Pop, returns 5, stack: [2] Stacks are useful for problems where we need to track previous elements efficiently.

Result

You can use a stack to store and retrieve elements in reverse order of insertion.

Understanding stack operations is key to managing the bars while scanning the histogram.

3

Intermediate

Using Stack to Track Increasing Bar Heights

🤔Before reading on: do you think we should push bars with decreasing heights onto the stack or only increasing heights? Commit to your answer.

Concept: We keep indices of bars in the stack only if their heights are increasing or equal, so we can find when a shorter bar ends a taller bar's rectangle.

We scan bars from left to right. For each bar: - If the stack is empty or current bar height is greater or equal to the bar at the top of the stack, push its index. - If current bar height is less, it means the previous taller bars can't extend further. We pop bars from the stack until the top bar is shorter or equal to current bar. - For each popped bar, we calculate the area with that bar as the smallest height. This way, the stack always holds indices of bars in increasing height order.

Result

Stack contains indices of bars with increasing heights, allowing us to find largest rectangles efficiently.

Maintaining increasing heights in the stack helps us know exactly when a rectangle ends and calculate its area.

4

Intermediate

Calculating Area When Popping Bars

🤔Before reading on: when popping a bar from the stack, do you think the width of the rectangle is from the start of the histogram or between certain indices? Commit to your answer.

Concept: When popping a bar, the width of the rectangle is between the current index and the index of the previous bar in the stack, not the entire histogram.

When we pop a bar at index 'top', the rectangle with height bars[top] extends from: - The index after the new top of the stack (if stack not empty) to - The current index (where we found a shorter bar) minus one. If the stack is empty after popping, the rectangle extends from the start (index 0) to current index minus one. Area = height of popped bar * width calculated this way. This calculation ensures we only consider consecutive bars taller or equal to the popped bar.

Result

We can calculate the largest rectangle area for each popped bar correctly using stack indices.

Knowing how to calculate width using stack indices is crucial for correct area computation.

5

Intermediate

Handling Remaining Bars After Full Scan

Concept: After scanning all bars, some bars remain in the stack and must be processed to find their largest rectangles.

Once we finish scanning all bars, the stack may still have indices. These bars extend to the end of the histogram. We pop each remaining bar and calculate area: - Width is from the index after the new top of the stack (or 0 if empty) to the last index of the histogram. - Calculate area as height * width. This step ensures no possible rectangle is missed.

Result

All bars are processed, and the largest rectangle area is found.

Processing remaining bars after scanning ensures completeness of the solution.

6

Advanced

Complete TypeScript Implementation with Stack

🤔Before reading on: do you think the stack stores bar heights or their indices? Commit to your answer.

Concept: Implement the largest rectangle algorithm in TypeScript using a stack that stores indices, not heights, for efficient area calculation.

```typescript function largestRectangleArea(heights: number[]): number { const stack: number[] = []; let maxArea = 0; const extendedHeights = [...heights, 0]; // Add zero height to flush stack at end for (let i = 0; i < extendedHeights.length; i++) { while (stack.length > 0 && extendedHeights[i] < extendedHeights[stack[stack.length - 1]]) { const height = extendedHeights[stack.pop()!]; const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1; maxArea = Math.max(maxArea, height * width); } stack.push(i); } return maxArea; } // Example usage: const histogram = [2, 1, 5, 6, 2, 3]; console.log(largestRectangleArea(histogram)); // Output: 10 ```

Result

The function prints 10, which is the largest rectangle area in the example histogram.

Storing indices instead of heights allows quick width calculation and efficient stack management.

7

Expert

Optimizations and Edge Cases in Stack Approach

🤔Before reading on: do you think adding a zero-height bar at the end is necessary? Why or why not? Commit to your answer.

Concept: Learn why adding a zero-height bar at the end simplifies the algorithm and how to handle edge cases like empty histograms or all bars equal height.

Adding a zero-height bar at the end forces the stack to empty by the end of the loop, ensuring all bars are processed without extra code. Edge cases: - Empty histogram returns 0 immediately. - All bars equal height means the largest rectangle is height * number of bars. - Strictly increasing or decreasing bars test stack push/pop behavior. These considerations make the algorithm robust and clean.

Result

Algorithm handles all edge cases correctly and runs efficiently with minimal code.

Understanding these subtle improvements prevents bugs and simplifies code in production.

Under the Hood

The stack keeps indices of bars in increasing height order. When a shorter bar appears, it signals the end of rectangles formed by taller bars before it. Popping from the stack gives the height of the rectangle, and the width is calculated using the current index and the new top of the stack. This method avoids checking all pairs by using the stack to remember boundaries efficiently.

Why designed this way?

The stack-based approach was designed to reduce the brute force O(n^2) complexity to O(n) by avoiding repeated area calculations. It leverages the property that rectangles extend until a shorter bar appears, and the stack efficiently tracks these boundaries. Alternatives like segment trees are more complex and slower for this problem.

Scan bars left to right

┌───────────────┐
│ Current bar i │
└──────┬────────┘
       │
       ▼
┌─────────────────────────────┐
│ Is current bar height < top │
│ of stack bar height?        │
└──────┬───────────────┬──────┘
       │               │
       ▼               ▼
Pop stack bar       Push current
Calculate area      index i
using popped bar

Repeat until stack empty or current bar taller

At end, pop remaining bars and calculate areas

Myth Busters - 3 Common Misconceptions

Quick: Do you think the stack stores bar heights directly? Commit to yes or no.

Common Belief: The stack stores the heights of bars to calculate areas.

Reality: The stack actually stores indices of bars, not their heights. Heights are accessed using these indices.

Why it matters: Storing heights directly would lose position information needed to calculate the width of rectangles, leading to incorrect area calculations.

Quick: Do you think the largest rectangle must include the tallest bar? Commit to yes or no.

Common Belief: The largest rectangle always includes the tallest bar in the histogram.

Reality: The largest rectangle may not include the tallest bar; it depends on the arrangement of bars. Sometimes shorter bars combined form a larger area.

Why it matters: Assuming the tallest bar is always part of the largest rectangle can mislead problem-solving and cause incorrect answers.

Quick: Do you think the algorithm needs to check every possible rectangle explicitly? Commit to yes or no.

Common Belief: We must check every possible group of bars to find the largest rectangle.

Reality: The stack algorithm cleverly avoids checking all groups by using the order of bars and popping when a shorter bar appears, achieving O(n) time.

Why it matters: Believing in brute force leads to inefficient solutions that don't scale for large histograms.

Expert Zone

1

The stack approach implicitly uses a monotonic stack pattern, which is a powerful technique for many range query problems beyond histograms.

2

Adding a sentinel zero-height bar at the end simplifies code by ensuring the stack empties without extra loops or checks.

3

The algorithm's correctness depends on careful width calculation using stack indices, which is a subtle but critical detail often overlooked.

When NOT to use

This stack method is ideal for static histograms. For dynamic histograms where bars change frequently, segment trees or binary indexed trees are better. Also, if bars have varying widths, this method does not apply directly.

Production Patterns

In production, this algorithm is used in image processing to find maximal rectangles, in financial analysis for stock span problems, and in UI layout engines to optimize space. It also serves as a foundation for more complex range maximum area queries.

Connections

Monotonic Stack

The largest rectangle algorithm is a classic example of using a monotonic stack to solve range problems.

Understanding this connection helps apply monotonic stacks to other problems like next greater element or sliding window maximum.

Dynamic Programming

Both approaches can solve largest rectangle problems, but stack method is more efficient and uses less memory.

Knowing the stack method complements dynamic programming and helps choose the best approach for similar problems.

Financial Stock Span Problem

The stack technique used here is similar to the one used in the stock span problem to find how many consecutive days a stock price was less or equal.

Recognizing this shared pattern allows reuse of stack logic across different domains.

Common Pitfalls

#1 Pushing bar heights instead of indices onto the stack.

Wrong approach:

stack.push(heights[i]); // Wrong: stores height, loses position info

Correct approach:

stack.push(i); // Correct: stores index to calculate width

Root cause:

Confusing the need for position information with just height values.

#2 Not adding a zero-height bar at the end to flush the stack.

Wrong approach:

for (let i = 0; i < heights.length; i++) { /* process without extra zero */ }

Correct approach:

const extendedHeights = [...heights, 0]; for (let i = 0; i < extendedHeights.length; i++) { /* process */ }

Root cause:

Forgetting that remaining bars in stack need to be processed after full scan.

#3 Calculating width incorrectly by using current index minus popped index.

Wrong approach:

const width = i - poppedIndex; // Incorrect width calculation

Correct approach:

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

Root cause:

Misunderstanding how to find the left boundary of the rectangle using the stack.

Key Takeaways

The largest rectangle in a histogram can be found efficiently using a stack to track increasing bar heights.

The stack stores indices, not heights, to calculate rectangle widths correctly.

When a shorter bar appears, popping taller bars from the stack lets us calculate areas of rectangles that end there.

Adding a zero-height bar at the end simplifies processing all bars without extra loops.

This stack approach runs in linear time, making it practical for large histograms and related range problems.

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