🌱 Keegan's Digital Garden

84. Largest Rectangle in Histogram

3 min read

📝 Problem Details

💭What Were My Initial Thoughts?

  • The naïve approach would be to check every possible rectangle using nested loops, but this results in O(n²) time complexity.
  • The key observation is that the largest rectangle for a given bar i extends until a smaller bar is encountered.
  • Using a monotonic stack, we can efficiently keep track of heights and their start positions:
    • If a new bar is taller, push it onto the stack (it could be part of a larger rectangle).
    • If a new bar is shorter, process and pop bars from the stack, calculating areas.
    • Ensure that remaining bars in the stack are processed at the end.
  • This allows us to find the largest rectangle in O(n) time.

💡 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 
- iterate 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;
    }
};

Graph View