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

Largest Rectangle in Histogram Using Stack

📖 Scenario: Imagine you have a row of buildings of different heights. You want to find the largest rectangular area that can fit inside the skyline formed by these buildings.

🎯 Goal: Build a program that finds the largest rectangle area in a histogram using a stack to keep track of building heights.

📋 What You'll Learn

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

Create a variable called stack initialized as an empty array

Use a for loop with variable i to iterate over heights and apply stack logic to find the largest rectangle

Print the largest rectangle area as a number

💡 Why This Matters

🌍 Real World

This technique helps in problems related to finding maximum areas in histograms, useful in image processing, stock span problems, and architectural design.

💼 Career

Understanding stack-based algorithms is important for software engineering roles that involve algorithm optimization and problem solving.

1

Create the histogram data

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

DSA Javascript

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

Hint

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

2

Initialize the stack and max area variable

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

DSA Javascript

const heights = [2, 1, 5, 6, 2, 3];
// Initialize stack and maxArea
// Your code here

Hint

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

3

Implement the stack logic to find the 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 the current height is less than the height at the top of the stack. Calculate area using popped height and update maxArea. Push i to stack when done.

DSA Javascript

const heights = [2, 1, 5, 6, 2, 3];
const stack = [];
let maxArea = 0;
// Implement the stack logic with a for loop
// Your code here

Hint

Remember to add a zero height at the end by checking if i === heights.length and use 0 as currentHeight.

4

Print the largest rectangle area

Write console.log(maxArea) to print the largest rectangle area found.

DSA Javascript

const heights = [2, 1, 5, 6, 2, 3];
const stack = [];
let maxArea = 0;
for (let i = 0; i  0 && currentHeight  maxArea) {
            maxArea = area;
        }
    }
    stack.push(i);
}
// Print the maxArea
// Your code here

Hint

Use console.log(maxArea) to show the result.

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