Largest Rectangle in Histogram Using Stack in DSA Javascript

Mental Model

We use a stack to keep track of bars that are not yet processed for the largest rectangle. When we find a bar shorter than the top of the stack, we calculate areas for bars taller than it.

Analogy: Imagine stacking books by height. When a shorter book arrives, you remove taller books from the stack to see how much shelf space they cover, calculating the biggest space used.

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: empty

Stack example:
[1] -> [2] -> [3] (indices of bars with increasing heights 1 -> 5 -> 6)

Dry Run Walkthrough

Input: histogram heights: [2, 1, 5, 6, 2, 3]

Goal: Find the largest rectangle area that fits inside 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 bars with 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), calculate area = 2 * 1 = 2
Stack: []

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

Step 3: Push index 1 (height 1) onto stack

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

Why: Stack empty, push current index

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

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

Why: Current bar taller than top of stack, push index

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

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

Why: Current bar taller than top of stack, push index

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

Popped index 3 (height 6), area = 6 * 1 = 6
Stack: [1, 2]

Why: Calculate area for bar taller than current smaller bar

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

Popped index 2 (height 5), area = 5 * 2 = 10
Stack: [1]

Why: Calculate area for bar taller than current smaller bar

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

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

Why: Current bar taller than top of stack, push index

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

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

Why: Current bar taller than top of stack, push index

Step 10: 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
Stack: []

Why: Calculate areas for all remaining bars to find max

Result:

Largest rectangle area = 10
Final stack empty

Annotated Code

DSA Javascript

class Histogram {
  constructor(heights) {
    this.heights = heights;
  }

  largestRectangleArea() {
    const stack = [];
    let maxArea = 0;
    const heights = this.heights;
    for (let i = 0; i <= heights.length; i++) {
      const currentHeight = i === heights.length ? 0 : heights[i];
      while (stack.length && currentHeight < heights[stack[stack.length - 1]]) {
        const topIndex = stack.pop();
        const height = heights[topIndex];
        const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
        const area = height * width;
        if (area > maxArea) maxArea = area;
      }
      stack.push(i);
    }
    return maxArea;
  }
}

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

for (let i = 0; i <= heights.length; i++) {

Traverse all bars plus one extra iteration to flush stack

const currentHeight = i === heights.length ? 0 : heights[i];

Use 0 height at end to pop all remaining bars

while (stack.length && currentHeight < heights[stack[stack.length - 1]]) {

Pop bars taller than current to calculate area

const topIndex = stack.pop();

Remove top bar index for area calculation

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

Calculate width of rectangle using current index and stack top

if (area > maxArea) maxArea = area;

Update max area if current area is larger

stack.push(i);

Push current bar index to stack

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 Javascript

for (let i = 0; i <= heights.length; i++) {

All bars same height

Calculates area as height * number of bars

DSA Javascript

while (stack.length && currentHeight < heights[stack[stack.length - 1]]) {

Strictly increasing heights

Bars pushed without popping until end flush

DSA Javascript

const currentHeight = i === heights.length ? 0 : heights[i];

When to Use This Pattern

When asked to find the largest rectangle in a histogram or similar structure, use a stack to track bars and calculate areas efficiently by popping taller bars when a shorter bar appears.

Common Mistakes

Mistake: Not pushing the extra 0 height bar at the end to flush stack
Fix: Add an iteration with height 0 after the last bar to pop all remaining bars

Mistake: Calculating width incorrectly by not considering stack top after pop
Fix: Calculate width as current index minus new stack top minus one, or current index if stack empty

Summary

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

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

The key insight is to use a stack to keep bars in increasing 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 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