---

1. Problem Summary

You are given an array heights, where each element represents the height of a bar in a histogram.
All bars have a width of exactly 1.

Your task is to compute the area of the largest rectangle that can be formed within the histogram, where:

• The rectangle must be continuous (formed by adjacent bars)
• The rectangle height is limited by the shortest bar within its span

Example interpretation:
If:

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

The largest rectangle has area:

5 × 2 = 10  (bars [5,6])
OR
6 × 2 = 12 (bars [5,6]; width 2, height 6? actually 6 * 1, but max is 10? no real max is 10? actually real answer is 10? real LC result is 10? No actual max is 10? Wait - actual max is 10? Actually the correct max is 10? No it's 10? No the real max is 10? Actually the largest rectangle is 10? NO the correct answer is 10? Wait: real LeetCode answer is **10**? Actually correct answer is **10**? Let's verify: heights [2,1,5,6,2,3]. Largest = 10.

So the result is:

10

---

2. Key Insights

1. Brute force is too slow

Checking all possible width and minimum heights would be:

O(N²) or O(N³)

Not acceptable for large input.

2. Each bar can be treated as the limiting height for some rectangle

The key is determining:

• how far left it can extend
• how far right it can extend
  before encountering a shorter bar.

3. A monotonic increasing stack solves this efficiently

We maintain indices of bars in ascending height order.

Why stack works:

• When a bar shorter than stack top appears,
• The stack top bar cannot extend further,
• So we compute its maximal rectangle.

4. We compute area when height boundary is known

Rectangle width formula for popped height:

width = currentIndex - previousSmallerIndex - 1

5. Append a zero-height bar at end

This flushes remaining stack bars automatically.

---

3. Approach

Monotonic Increasing Stack Algorithm

Steps:

1. Initialize empty stack to hold indices.
2. Loop through all indices i from 0 to n:
   • Treat height = 0 for artificial final index.
3. For each height:
   • While stack not empty AND current height < height at stack top:
     • pop index from stack
     • compute height = heights[popped]
     • compute width: if stack empty: width = i else: width = i - stack.peek() - 1
     • compute area = height × width
     • update maxArea
   • Push current index onto stack
4. Return maxArea

---

4. Time and Space Complexity

Time Complexity:

O(N)

Each bar pushed and popped at most once.

Space Complexity:

O(N)

Stack stores indices in worst case.

---

5. Java Solution

import java.util.Stack;

class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;

        for (int i = 0; i <= heights.length; i++) {
            int currentHeight = (i == heights.length) ? 0 : heights[i];

            while (!stack.isEmpty() && currentHeight < heights[stack.peek()]) {
                int height = heights[stack.pop()];
                int width;
                if (stack.isEmpty()) {
                    width = i;
                } else {
                    width = i - stack.peek() - 1;
                }
                maxArea = Math.max(maxArea, height * width);
            }

            stack.push(i);
        }

        return maxArea;
    }
}

---

6. Dry Run Examples

Example 1

Input:

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

Processing outline:

• push 0
• height drops at index 1 → compute for 2
• push 1
• push 2
• push 3
• height drops at index 4 → compute for 6 then 5
• continue…
  Final result:

10

---

Example 2

Input:

[2,4]

Rectangles:

• height 2 width 2 → area 4
• height 4 width 1 → area 4

Output:

4

---

Example 3

Input:

[1,1,1,1]

Largest rectangle is whole width:

1 × 4 = 4

Output:

4

---

Example 4

Input:

[4,3,2,1]

Best rectangle:

2 × 2 = 4   OR 3 × 1 = 3, etc.

Output:

4

---

Example 5

Input:

[6,2,5,4,5,1,6]

Correct max area:

12

---

7. Why This Solution Works

• Stack maintains increasing height order
• A bar’s largest rectangle is found exactly when a shorter bar arrives
• Each bar is processed once
• No redundant comparisons
• Efficient boundary determination

---

8. Common Mistakes

1. Forgetting to append artificial zero height at end
2. Incorrect width calculation after popping
3. Assuming rectangles must include current index
4. Using brute force thinking it’s acceptable
5. Confusing height vs index in stack