112. Largest Rectangle in Histogram

🔗 LeetCode Problem: 84. Largest Rectangle in Histogram
📊 Difficulty: Hard
🏷️ Topics: Stack, Array, Monotonic Stack

Problem Statement

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1:

Input: heights = [2,1,5,6,2,3]
Output: 10

Example 2:

Input: heights = [2,4]
Output: 4

Constraints: - 1 <= heights.length <= 10^5 - 0 <= heights[i] <= 10^4

🌟 Understanding the Problem - Visual First!

Let me start by showing you what we're looking for.

heights = [2, 1, 5, 6, 2, 3]

Visual histogram:
        6
      5 █
    2 █ █
  1 █ █ █   3
  █ █ █ █ 2 █
  █ █ █ █ █ █
  ─────────────
  0 1 2 3 4 5

What rectangles can we form?

Some examples:

Rectangle 1: Using height 1
  ████████████
  █ █ █ █ █ █
  0 1 2 3 4 5
  Height: 1, Width: 6, Area: 1 × 6 = 6

Rectangle 2: Using height 2
    █████████
  █ █ █ █ █ █
  0 1 2 3 4 5
  Height: 2, Width: 3 (indices 0, 4, 5), Area: 2 × 3 = 6

Rectangle 3: Using height 5
      █████
      █ █
      2 3
  Height: 5, Width: 2 (indices 2, 3), Area: 5 × 2 = 10 ✓ LARGEST!

💡 The Core Question

For EACH bar, ask: "How big a rectangle can I form if I use THIS bar's height?"

Let's pick the bar at index 2 (height 5):

        6
      5 █
      █ █
      █ █
      █ █
      ─────
      2 3

Question: Using height 5, how far can I extend left and right?

LEFT: Can I include index 1? 
  No! Index 1 has height 1, which is < 5

RIGHT: Can I include index 3?
  Yes! Index 3 has height 6, which is >= 5

RIGHT: Can I include index 4?
  No! Index 4 has height 2, which is < 5

So with height 5:
  I can use indices: 2, 3 (width = 2)
  Area = 5 × 2 = 10 ✓

The rule: A bar with height H can extend to adjacent bars that have height >= H

🎯 The Brute Force Approach (Understanding First)

Let me show you the straightforward way first to build intuition.

For EACH bar:
  1. Expand LEFT as far as possible (while height >= current height)
  2. Expand RIGHT as far as possible (while height >= current height)
  3. Calculate area = height × width
  4. Track maximum

Example: Bar at index 3 (height 6)

heights = [2, 1, 5, 6, 2, 3]
                    ↑
                 index 3

Step 1: Expand LEFT from index 3
  Check index 2: height 5 < 6? Yes, STOP
  Can't include index 2

Step 2: Expand RIGHT from index 3
  Check index 4: height 2 < 6? Yes, STOP
  Can't include index 4

Result: Only index 3 itself
  Width = 1
  Area = 6 × 1 = 6

Example: Bar at index 2 (height 5)

heights = [2, 1, 5, 6, 2, 3]
                 ↑
              index 2

Step 1: Expand LEFT from index 2
  Check index 1: height 1 < 5? Yes, STOP
  Can't include index 1

Step 2: Expand RIGHT from index 2
  Check index 3: height 6 >= 5? Yes, INCLUDE!
  Check index 4: height 2 < 5? Yes, STOP

Result: Indices 2 and 3
  Width = 2
  Area = 5 × 2 = 10 ✓

Problem with brute force: O(n²) - too slow for large inputs!

🔑 The Key Insight for Optimization

WHEN do we know a bar's maximum rectangle?

Critical observation:

We KNOW a bar's full extent when we encounter a SHORTER bar!

Example:
  heights = [2, 1, 5, 6, 2, 3]
                       ↑  ↑
                       6  2

When we reach index 4 (height 2):
  - Bar at index 3 (height 6) CANNOT extend to index 4
  - Bar at index 2 (height 5) CANNOT extend to index 4

We can NOW calculate their maximum rectangles!

Think about it this way:

As we go left to right:

Heights: 2, 1, 5, 6, ???

At index 3, we have bars going up: 2, 1, 5, 6
  Can these extend further right? Maybe!
  We don't know yet...

But when we see the next bar is 2:
  Heights: 2, 1, 5, 6, 2

  NOW we know:
  - Height 6 STOPS before index 4
  - Height 5 STOPS before index 4

  Time to calculate their rectangles!

🎨 Building the Intuition: The Stack Approach

Why Do We Need a Stack?

The insight: When we see a shorter bar, we need to "wrap up" all taller bars.

heights = [2, 1, 5, 6, 2, 3]

As we process left to right:

Index 0 (height 2): Keep it, might extend
Index 1 (height 1): Shorter! Process 2, keep 1
Index 2 (height 5): Taller, keep it
Index 3 (height 6): Taller, keep it
Index 4 (height 2): Shorter! Process 6 and 5

The stack helps us remember which bars are "waiting" to find their right boundary.

What Information Do We Need?

To calculate a bar's maximum rectangle, we need:

1. The bar's HEIGHT - Easy, we have it!
2. How far LEFT it extends
3. How far RIGHT it extends

The RIGHT boundary is easy: It's the current index (where we found shorter bar)

The LEFT boundary is tricky: How far back does it extend?

Here's the MAGIC of the stack:

When we see bars in INCREASING order, they all can extend together!

Example: heights = [2, 5, 6]
         Stack after processing: [2, 5, 6] (imagine)

Why? Because:
  - 5 can extend back to include 2 (2 <= 5)
  - 6 can extend back to include 5 and 2 (both <= 6)

When we pop a bar, the NEXT bar in stack tells us the LEFT boundary!

🎯 The Stack Mechanism - Step by Step

Let me explain what the stack ACTUALLY does.

Rule 1: Stack Stores INDICES (Not Heights!)

Why indices?
  Because we need to calculate WIDTH!

  Width = rightIndex - leftIndex - 1

  We need positions, not just heights!

Rule 2: Stack Keeps INCREASING Heights

We only keep bars that are SHORTER than or EQUAL to the current bar.

When we see a TALLER bar → Push it (might extend further)
When we see SHORTER bar → Pop all taller bars (they can't extend)

Rule 3: What Each Pop Tells Us

When we POP an index from the stack:

popped = the bar we're calculating area for
current = the position where we found shorter bar (RIGHT boundary)
stack.top = the LEFT boundary (after popping)

Width = current - stack.top - 1

🔍 Intuition Through Example

Let me walk through heights = [2, 1, 5, 6, 2, 3] focusing on INTUITION.

Visual:
        6
      5 █
    2 █ █
  1 █ █ █   3
  █ █ █ █ 2 █
  █ █ █ █ █ █
  ─────────────
  0 1 2 3 4 5

Processing Index 0 (height 2):

Stack: []
Current: height 2

Is stack empty or 2 > stack.top? 
  Stack is empty, so just push.

Stack after: [0]
Meaning: "Index 0 is waiting to find its right boundary"

Processing Index 1 (height 1):

Stack: [0]
Current: height 1

Is 1 > heights[0]=2? No! 1 < 2
  So height 2 CANNOT extend to index 1!

Time to calculate area for index 0:
  Pop index 0 (height 2)
  RIGHT boundary: current index = 1
  LEFT boundary: stack is now empty, so can extend to start
  Width: 1 - 0 = 1 (just index 0)
  Area: 2 × 1 = 2

Now push index 1:

Stack after: [1]
Meaning: "Index 1 is waiting"

Processing Index 2 (height 5):

Stack: [1]
Current: height 5

Is 5 > heights[1]=1? Yes!
  So push it.

Stack after: [1, 2]
Meaning: "Both index 1 and 2 are waiting"

Key insight: 5 can extend back to include 1!
  Because 1 <= 5

Processing Index 3 (height 6):

Stack: [1, 2]
Current: height 6

Is 6 > heights[2]=5? Yes!
  So push it.

Stack after: [1, 2, 3]
Meaning: "All three waiting"

Key insight: 6 can extend back to include 5 and 1!
  Because all are <= 6

Processing Index 4 (height 2) - THE KEY MOMENT:

Stack: [1, 2, 3]
Current: height 2

Is 2 > heights[3]=6? No! 2 < 6
  Height 6 CANNOT extend to index 4!

POP and calculate for index 3 (height 6):
  Height: 6
  RIGHT boundary: index 4 (current)
  LEFT boundary: stack.top after pop = index 2

  Width calculation:
    From where to where?
    Bar at index 3 can extend from AFTER index 2 to BEFORE index 4
    That's just index 3 itself!
    Width = 4 - 2 - 1 = 1

  Area: 6 × 1 = 6

Stack after pop: [1, 2]

Is 2 > heights[2]=5? No! 2 < 5
  Height 5 also CANNOT extend to index 4!

POP and calculate for index 2 (height 5):
  Height: 5
  RIGHT boundary: index 4 (current)
  LEFT boundary: stack.top after pop = index 1

  Width calculation:
    From where to where?
    Bar at index 2 can extend from AFTER index 1 to BEFORE index 4
    That's indices 2 and 3!
    Width = 4 - 1 - 1 = 2

  Area: 5 × 2 = 10 ✓ MAXIMUM!

Stack after pop: [1]

Is 2 > heights[1]=1? Yes!
  Push index 4

Stack after: [1, 4]

Processing Index 5 (height 3):

Stack: [1, 4]
Current: height 3

Is 3 > heights[4]=2? Yes!
  Push it

Stack after: [1, 4, 5]

End of Array - Process Remaining:

Stack: [1, 4, 5]

These bars never found a shorter bar to their right!
They extend all the way to the end.

Pop each and calculate...
(I'll skip details, but same logic applies)

🎯 The Critical Width Formula

Understanding: width = currentIndex - stack.peek() - 1

This is confusing! Let me explain with a visual.

When we pop index h:

Situation:
  ... [leftBoundary] ... [h] ... [rightBoundary]
      stack.peek()              currentIndex

The bar at index h can extend:
  - From AFTER leftBoundary
  - To BEFORE rightBoundary

Example: leftBoundary=1, h=2, rightBoundary=4

  Indices: 0  1  2  3  4  5
  Heights: █  █  █  █  █  █
              ↑  ↑  ↑  ↑
           left h  ok  right

Bar at index 2 can include: index 2 and 3
Count: 2 bars

Formula: 4 - 1 - 1 = 2 ✓

Why the -1?
  Because we want bars BETWEEN the boundaries,
  not including the boundaries themselves!

Special case: Stack empty after pop

If stack is empty after popping:
  No left boundary! Can extend all the way to start.

  Width = currentIndex (from 0 to current)

💻 The Algorithm (Now That We Understand)

import java.util.Stack;

class Solution {
  public int largestRectangleArea(int[] heights) {
    int len = heights.length;
    if(len == 1) {
      return heights[0];
    }

    // Approach - lets maintain monotonic stack of increasing order of heights.
    // Gotcha: when stack.isEmpty(), left boundary should be -1.
    Stack<Integer> stack = new Stack<>();
    int res = Integer.MIN_VALUE;

    for(int i = 0; i < len; i++) {
      if(stack.isEmpty() || heights[stack.peek()] < heights[i]) {
        // for [2,1,5,6,2,3] => indices 1, 2, 3 would be pushed.
        stack.push(i);
      } else {
        // for [2,1,5,6,2,3] => indices 1, 2, 3 are pushed.
        // Now 2 came which is less than 6. So, 6 cannot proceed right side. End of 6 to extend on right side.
        // So, pop 6 out and calculate its area it can extend.
        while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
          int indexPopped = stack.pop(); // 3
          int rightBoundary = i; // current index itself as 6 cannot extend which is 4.
          int leftBoundary = stack.isEmpty() ? -1 : stack.peek(); // that is 2. As 5 which is lesser than 6 and 6 cannot extend lefter than 5.
          int width = rightBoundary - leftBoundary - 1; // 4 - 2 - 1 = 1
          int area = width * heights[indexPopped]; // as we are caculating for the popped number.
          // System.out.println("For index "+indexPopped+" which has height "+heights[indexPopped]+": "+area);
          res = Math.max(res, area);
        }

        // we need to push the existing one finally.
        // This way, we calculate height of each bar.
        stack.push(i);
      }
    }

    // We need to check for remaining heights left on the stack.
    // For [2,1,5,6,2,3], stack would be left with indices [1,4,5] as
    // 1 do not have a lesser element than itself on the right side.
    // 2 do not have a lesser element than itself on the right side.
    // 3 do not have a lesser element than itself on the right side.
    while (!stack.isEmpty()) {
      int indexPopped = stack.pop();
      int rightBoundary = len;
      int leftBoundary = stack.isEmpty() ? -1 : stack.peek();
      int width = rightBoundary - leftBoundary - 1;
      int area = width * heights[indexPopped];
      res = Math.max(res, area);
    }

    return res;
  }

  public static void main(String[] args) {
    Solution s = new Solution();
    System.out.println(s.largestRectangleArea(new int[] {2,1,5,6,2,3}) == 10);
    System.out.println(s.largestRectangleArea(new int[] {2,4}) == 4);
    System.out.println(s.largestRectangleArea(new int[] {1}) == 1);
    System.out.println(s.largestRectangleArea(new int[] {1, 1}) == 2);
  }
}

🎯 Why This Works - Final Summary

The Intuition:

Increasing heights can all potentially extend together
When we see shorter height, we know taller bars stop there
Stack remembers which bars are still waiting for right boundary
When we pop, we calculate that bar's maximum rectangle
Stack top after pop tells us the left boundary

The Magic:

Stack maintains bars in increasing order:
  - Next element in stack = nearest shorter bar on left
  - Current index = first shorter bar on right
  - These two define the rectangle boundaries!

⚠️ Common Mistakes

Mistake 1: Thinking boundaries are "first shorter"

❌ WRONG THINKING:
"Find first bar shorter than current on left"

✓ CORRECT THINKING:
"When we pop a bar, stack.top IS its left boundary"
"Current index IS its right boundary"

The stack AUTOMATICALLY gives us these!

Mistake 2: Not using sentinel

❌ Without sentinel:
Need separate loop to process remaining stack

✓ With sentinel (height 0 at end):
Forces all bars to be popped naturally
Cleaner code!

Mistake 3: Confusing what's on stack

❌ Stack stores heights
✓ Stack stores INDICES

We need indices to calculate width!

📝 Key Takeaways

Problem: For each bar, find maximum rectangle using that height
Observation: We know a bar's extent when we find shorter bar
Stack: Keeps bars in increasing order, waiting for right boundary
Pop trigger: Current bar is shorter
Left boundary: Stack top after popping
Right boundary: Current index
Width: currentIndex - stack.peek() - 1

Time: O(n) - Each bar pushed/popped once
Space: O(n) - Stack storage

🎯 Final Intuition Check

Ask yourself:

Why stack? To remember bars waiting for their right boundary
Why increasing? Shorter bars can't extend beyond taller bars
When to pop? When current is shorter (taller bars stop here)
What does pop give us? The bar whose max rectangle we calculate
Where are boundaries? Stack top (left), current index (right)

If you understand these 5 points, you've got it! 🎉

Happy practicing! 🎯

Note: This is genuinely one of the hardest stack problems. The key is understanding WHY the stack gives us boundaries automatically. Don't memorize the code - understand the intuition! 💪✨