LeetCode Solution 84 - Largest Rectangle in Histogram

Problem Statement

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

Example

Input:

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

Output:

 10

---

Optimal Approach: Monotonic Stack

The most efficient way to solve this problem is by using a Monotonic Stack to efficiently determine the maximum rectangular area.

Algorithm Steps:

1. Initialize an empty stack.
2. Iterate through the heights array:
   • While the stack is not empty and the current height is smaller than the height at the top index of the stack, calculate the area.
   • Push the current index onto the stack.
3. After iteration, process any remaining heights in the stack.

---

LeetCode-Compatible C++ Solution

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<int> st;
        int maxArea = 0;
        heights.push_back(0); // Sentinel value to process all bars
        
        for (int i = 0; i < heights.size(); i++) {
            while (!st.empty() && heights[i] < heights[st.top()]) {
                int h = heights[st.top()];
                st.pop();
                int width = st.empty() ? i : i - st.top() - 1;
                maxArea = max(maxArea, h * width);
            }
            st.push(i);
        }
        return maxArea;
    }
};

---

Step-by-Step Explanation

1. Stack Maintenance: The stack stores indices of increasing heights.
2. Area Calculation: When a smaller height is encountered, pop from the stack and calculate area using the last popped height.
3. Final Processing: The sentinel value ensures that all heights are processed.

---

Dry Run with Sample Input

Given Input:

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

Execution:

Step	Stack (Indices)	Action
0	[0]	Push 0
1	[1]	Pop 0, Push 1
2	[1,2]	Push 2
3	[1,2,3]	Push 3
4	[1,4]	Pop 3, 2; Push 4
5	[1,4,5]	Push 5
6	[1]	Pop 5, 4; Compute Max Area

Total Maximum Area: 10

---

Alternative Approaches

1. Brute Force (Checking All Rectangles)

• Time Complexity: O(N²)
• Space Complexity: O(1)
• Why Not? Too slow for large inputs.

2. Using Divide and Conquer (Segment Tree)

• Time Complexity: O(N log N)
• Space Complexity: O(N)
• Why Not? Complex implementation compared to stack.

3. Dynamic Programming (Precomputing Left & Right Boundaries)

• Time Complexity: O(N)
• Space Complexity: O(N)
• Why Not? Uses extra space compared to stack.

---

Best Solution: Monotonic Stack

Approach	Time Complexity	Space Complexity	Efficiency
Brute Force	O(N²)	O(1)	❌ Slow
Divide & Conquer	O(N log N)	O(N)	❌ Complex
Dynamic Programming	O(N)	O(N)	❌ Extra Space
Monotonic Stack	O(N)	O(N)	✅ Best

The monotonic stack is the best approach since it processes each element efficiently in O(N) time while using minimal extra space.

---

Conclusion

The Monotonic Stack approach provides an optimal O(N) solution for the Largest Rectangle in Histogram problem. It efficiently determines the maximum rectangular area without unnecessary calculations.

Similar Problems for Practice:

1. Maximal Rectangle
2. Trapping Rain Water
3. Largest Square in Matrix

This problem is a great example of leveraging stacks to efficiently solve range-based problems.