Day 5 - Histogram Max Rectangular Area.md

Difficulty	Hard
Source	160 Days of Problem Solving
Tags	Stack

🚀 Day 5. Histogram Max Rectangular Area 🧠

The problem can be found at the following link: Question Link

💡 Problem Description:

You are given a histogram represented by an array arr, where each element denotes the height of the bars.
Each bar has a width of 1 unit.

Your task is to find the largest rectangular area possible in the given histogram, where the rectangle is formed using contiguous bars.

🔍 Example Walkthrough:

Example 1:

Input:

arr[] = [60, 20, 50, 40, 10, 50, 60]

Output:

100

Explanation:

The maximum area is achieved by picking bars 50 and 60.
The area is computed as:
$[ \text{(smallest height)} \times \text{(number of picked bars)} = 50 \times 2 = 100 $]

Example 2:

Input:

arr[] = [3, 5, 1, 7, 5, 9]

Output:

15

Explanation:

The maximum area is achieved by picking bars 7, 5, and 9.
$[ 5 \times 3 = 15 $]

Example 3:

Input:

arr[] = [3]

Output:

3

Explanation:

The largest area is simply 3 (height 3, width 1).

Constraints:

• $(1 \leq \text{arr.size()} \leq 10^5)$
• $(0 \leq \text{arr[i]} \leq 10^4)$

🎯 My Approach:

Optimized Monotonic Stack (O(N) Time, O(N) Space)

1. Use a stack to keep track of indices of increasing heights.
2. Process each bar once, ensuring an O(N) complexity.
3. Calculate maximum width dynamically by maintaining left and right boundaries.

Algorithm Steps:

1. Traverse each element in arr[] and use a monotonic increasing stack to store indices.
2. If arr[i] is smaller than the top of the stack, compute the largest area with the popped height.
3. The width is determined by checking the previous elements stored in the stack.
4. Repeat the process until all elements are processed.

🕒 Time and Auxiliary Space Complexity

• Expected Time Complexity: O(N), as each bar is processed only once.
• Expected Auxiliary Space Complexity: O(N), due to stack storage.

📝 Solution Code

Code (C++)

class Solution {
public:
    int getMaxArea(vector<int>& arr) {
        stack<int> s;
        int n = arr.size(), res = 0;
        for (int i = 0; i <= n; i++) {
            while (!s.empty() && (i == n || arr[s.top()] >= arr[i])) {
                int h = arr[s.top()];
                s.pop();
                int w = s.empty() ? i : i - s.top() - 1;
                res = max(res, h * w);
            }
            s.push(i);
        }
        return res;
    }
};

⚡ Alternative Approaches

2️⃣ Optimized Two-Pass Stack (O(N) Time, O(N) Space)

Approach:

1. Compute left and right limits for each histogram bar separately.
2. Store smallest previous and next smaller elements in arrays.
3. Compute the maximum area using (right - left + 1) × height formula.

class Solution {
public:
    int getMaxArea(vector<int>& arr) {
        int n = arr.size();
        vector<int> left(n), right(n);
        stack<int> s;

        for (int i = 0; i < n; i++) {
            while (!s.empty() && arr[s.top()] >= arr[i]) s.pop();
            left[i] = s.empty() ? 0 : s.top() + 1;
            s.push(i);
        }

        while (!s.empty()) s.pop();

        for (int i = n - 1; i >= 0; i--) {
            while (!s.empty() && arr[s.top()] >= arr[i]) s.pop();
            right[i] = s.empty() ? n - 1 : s.top() - 1;
            s.push(i);
        }

        int res = 0;
        for (int i = 0; i < n; i++)
            res = max(res, arr[i] * (right[i] - left[i] + 1));

        return res;
    }
};

🔹 Pros: Precomputes left and right boundaries separately, reducing stack operations.
🔹 Cons: Uses extra space O(N) for left and right arrays.

📊 Comparison of Approaches

Approach	⏱️ Time Complexity	🗂️ Space Complexity	✅ Pros	⚠️ Cons
+Monotonic Stack - Single Pass (Optimized In-Place Approach)	🟢 O(N)	🟡 O(N)	Simple stack approach	Uses extra memory for stack
Monotonic Stack - Two Pass (Left-Right Boundaries Precomputed)	🟢 O(N)	🟢 O(1)	Best runtime & space efficiency	Slightly harder to grasp

💡 Best Choice?

• ✅ For lowest memory usage: Two-Pass Stack (O(N), O(1)).
• ✅ For clarity: Left-Right Boundary Arrays (O(N), O(N)).

Code (Java)

class Solution {
    public int getMaxArea(int[] arr) {
        Stack<Integer> s = new Stack<>();
        int n = arr.length, res = 0;
        for (int i = 0; i <= n; i++) {
            while (!s.isEmpty() && (i == n || arr[s.peek()] >= arr[i])) {
                int h = arr[s.pop()];
                int w = s.isEmpty() ? i : i - s.peek() - 1;
                res = Math.max(res, h * w);
            }
            s.push(i);
        }
        return res;
    }
}

Code (Python)

class Solution:
    def getMaxArea(self, arr):
        stack, n, res = [], len(arr), 0
        for i in range(n + 1):
            while stack and (i == n or arr[stack[-1]] >= arr[i]):
                h = arr[stack.pop()]
                w = i if not stack else i - stack[-1] - 1
                res = max(res, h * w)
            stack.append(i)
        return res

🎯 Contribution and Support:

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count