Largest Rectangle in Histogram Using Stack in DSA Typescript - Build from Scratch

Largest Rectangle in Histogram Using Stack

📖 Scenario: You are working with a histogram that shows the heights of bars side by side. Each bar's height is a number. You want to find the largest rectangle that can fit inside the histogram. This is useful in many real-world cases like finding the largest area of land in a skyline or analyzing data peaks.

🎯 Goal: Build a program that uses a stack to find the largest rectangle area in a histogram represented by an array of bar heights.

📋 What You'll Learn

Create an array called heights with exact values: [2, 1, 5, 6, 2, 3]

Create a variable called stack as an empty array to store indices

Use a for loop with variable i to iterate over heights plus one extra iteration

Inside the loop, use a while loop to pop from stack when current height is less than height at top of stack

Calculate area using popped height and width based on current index and stack top

Keep track of the maximum area in a variable called maxArea

Print the final maxArea after processing all bars

💡 Why This Matters

🌍 Real World

Finding the largest rectangle in a histogram is useful in image processing, land area analysis, and stock market data visualization.

💼 Career

This problem teaches stack usage and efficient area calculation, skills valuable for software engineers working on performance-critical applications and data analysis.

1

Create the histogram data

Create an array called heights with these exact values: [2, 1, 5, 6, 2, 3]

DSA Typescript

// Create the array heights with the given values
// Your code here

Hint

Use const heights: number[] = [2, 1, 5, 6, 2, 3]; to create the array.

2

Setup stack and maxArea variables

Create a variable called stack as an empty array of numbers and a variable called maxArea set to 0

DSA Typescript

const heights: number[] = [2, 1, 5, 6, 2, 3];
// Create stack as empty number array and maxArea as 0
// Your code here

Hint

Use const stack: number[] = []; and let maxArea: number = 0;.

3

Implement the main loop to calculate largest rectangle

Use a for loop with variable i from 0 to heights.length inclusive. Inside the loop, use a while loop to pop from stack while stack is not empty and current height is less than height at top of stack. Calculate area using popped height and width based on i and top of stack. Update maxArea if the new area is larger. After the while loop, push i to stack.

DSA Typescript

const heights: number[] = [2, 1, 5, 6, 2, 3];
const stack: number[] = [];
let maxArea: number = 0;
// Add for loop and while loop logic here
// Your code here

Hint

Remember to add one extra iteration with i <= heights.length and treat height as 0 at that point.

4

Print the largest rectangle area

Write a console.log statement to print the value of maxArea

DSA Typescript

const heights: number[] = [2, 1, 5, 6, 2, 3];
const stack: number[] = [];
let maxArea: number = 0;

for (let i = 0; i  0 && currentHeight  maxArea) {
            maxArea = area;
        }
    }
    stack.push(i);
}
// Print maxArea
// Your code here

Hint

Use console.log(maxArea); to show the largest rectangle area.

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