84. Largest Rectangle in Histogram

📝 Problem Details

• Title: 84. Largest Rectangle in Histogram
• Link: https://leetcode.com/problems/largest-rectangle-in-histogram/
• Difficulty: Hard
• Tags/Categories: Stack Monotonic-Stack

💭What Were My Initial Thoughts?

- 

🤔What Did I Struggle With?

~

💡 Explanation of Solution

- create a vector of pairs where the pair contains 
	- the starting index for the value 
	- the value itself 

- keep a max result variable which will track the largest rectangle by area 
- tterate through the `heights` array.
- for each bar at index `i`:
    - set the initial `start` position to `i` (where the rectangle can begin).
    - while the stack is not empty and the current bar height is less than the height at the top of the stack:**
        - calculate the rectangle area for the height at the top of the stack.
            - compute the `width` as `i - index` (distance from the current index to the index at the stack's top).
            - compute the area as `height * width`.
            - update `result` with the maximum area found so far.
        - update the `start` index to the `index` popped from the stack.
    - push the current bar with the updated `start` index onto the stack.

- process the remaining elements in the stack 
	- for each remaining element in the stack
		- calculate the rectangle area using the height of the current bar and the width as the difference between the end of the histogram and the start index stored in the stack 

- return the max result 

⌛ Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

💻 Implementation of Solution

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        stack<pair<int, int>> stk;
        int result = 0;
 
        for(int i=0; i < heights.size(); i++){
            int start = i;
 
            while(!stk.empty() && stk.top().second > heights[i]){
               int index = stk.top().first;
               int width = i - index;
               int height = stk.top().second;
               stk.pop();
 
               result = max(result, width * height);
               start = index;
            }
 
            stk.push({start, heights[i]});
        }
 
 
        while(!stk.empty()){
            int width = heights.size() - stk.top().first;
            int height = stk.top().second;
            stk.pop();
            result = max(result, height * width);
        }
 
        return result;
    }
};