Keyboard shortcuts

Press or to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Largest Rectangle In Histogram 🧠

LeetCode Link: Largest Rectangle In Histogram

Difficulty: Hard

Problem Explanation 📝

Problem: LeetCode 84 - Largest Rectangle in Histogram

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

Intuition: To find the largest rectangle in a histogram, we can utilize a stack to keep track of the indices of increasing heights. By iterating through the histogram, we can calculate the area of each rectangle formed by the heights.

Approach:

  1. Initialize a stack to store the indices of increasing heights.
  2. Initialize the maximum area to 0.
  3. Iterate through each bar in the histogram:
  • While the stack is not empty and the current bar's height is less than the height at the index at the top of the stack:
  • Pop the index from the stack and calculate the area of the rectangle formed by the popped bar.
  • Update the maximum area if the calculated area is greater.
  • Push the current index onto the stack.
  1. After iterating through all bars, there might be remaining bars in the stack. Process them similarly to step 3 to calculate the areas and update the maximum area.
  2. Return the maximum area.

Time Complexity: The time complexity is O(n), where n is the number of bars in the histogram. We iterate through each bar once.

💾 Space Complexity: The space complexity is O(n), where n is the number of bars in the histogram. In the worst case, all bars are stored in the stack.

Solutions 💡

Cpp 💻

#include<bits/stdc++.h>
using namespace std;

class Solution {
  public:
    int largestRectangleArea(vector<int> &heights) {
        int n = heights.size();
        stack<int> stack;
        int maxArea = 0;

        for (int i = 0; i <= n; ++i) {
            while (!stack.empty() && (i == n || heights[i] < heights[stack.top()])) {
                int height = heights[stack.top()];
                stack.pop();
                int width = stack.empty() ? i : i - stack.top() - 1;
                maxArea = max(maxArea, height * width);
            }

            stack.push(i);
        }

        return maxArea;
    }
};

Python 🐍

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack = []
        max_area = 0

        for i in range(len(heights)):
            while stack and heights[i] < heights[stack[-1]]:
                height = heights[stack.pop()]
                width = i if not stack else i - stack[-1] - 1
                max_area = max(max_area, height * width)
            stack.append(i)

        while stack:
            height = heights[stack.pop()]
            width = len(heights) if not stack else len(heights) - stack[-1] - 1
            max_area = max(max_area, height * width)

        return max_area