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:
- Initialize a stack to store the indices of increasing heights.
- Initialize the maximum area to 0.
- 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.
- 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.
- 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