In this post, we are going to solve the Largest Rectangle in Histogram Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.

Problem
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.
Example 1:
Input: heights = [2,1,5,6,2,3] Output: 10 Explanation: The above is a histogram where width of each bar is 1. The largest rectangle is shown in the red area, which has an area = 10 units.
Example 2:
Input: heights = [2,4] Output: 4
Constraints:
1 <= heights.length <= 105
0 <= heights[i] <= 104
Now, let’s see the leetcode solution of Largest Rectangle in Histogram Leetcode Solution.
Largest Rectangle in Histogram Leetcode Solution in Python
class Solution: def largestRectangleArea(self, heights: List[int]) -> int: ans = 0 stack = [] for i in range(len(heights) + 1): while stack and (i == len(heights) or heights[stack[-1]] > heights[i]): h = heights[stack.pop()] w = i - stack[-1] - 1 if stack else i ans = max(ans, h * w) stack.append(i) return ans
Largest Rectangle in Histogram Leetcode Solution in CPP
class Solution { public: int largestRectangleArea(vector<int>& heights) { int ans = 0; stack<int> stack; for (int i = 0; i <= heights.size(); ++i) { while (!stack.empty() && (i == heights.size() || heights[stack.top()] > heights[i])) { const int h = heights[stack.top()]; stack.pop(); const int w = stack.empty() ? i : i - stack.top() - 1; ans = max(ans, h * w); } stack.push(i); } return ans; } };
Largest Rectangle in Histogram Leetcode Solution in Java
class Solution { public int largestRectangleArea(int[] heights) { int ans = 0; Deque<Integer> stack = new ArrayDeque<>(); for (int i = 0; i <= heights.length; ++i) { while (!stack.isEmpty() && (i == heights.length || heights[stack.peek()] > heights[i])) { final int h = heights[stack.pop()]; final int w = stack.isEmpty() ? i : i - stack.peek() - 1; ans = Math.max(ans, h * w); } stack.push(i); } return ans; } }
Note: This problem Largest Rectangle in Histogram is generated by Leetcode but the solution is provided by Chase2learn This tutorial is only for Educational and Learning purposes.