Largest Rectangle in Histogram LeetCode Solution
Largest Rectangle in Histogram LeetCode Solution
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.
- 1 <= heights.length <= 105
- 0 <= heights[i] <= 104
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.
Largest Rectangle in Histogram LeetCode Solution:
Given an array of integersheights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.
Constraints :
1 <= heights.length <= 105
0 <= heights[i] <= 104
Example 2:
Input: heights = [2,4]
Output: 4
Complexity:
The time complexity of this solution is O(n), where n is the number of elements in the heights vector. This is because each bar is processed only once.
Output: The space complexity is O(n) as well because we use two additional arrays of size n, nsr and nsl, and a stack to store indices.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Largest Rectangle in Histogram LeetCode Solution:
C++
Java
Python
C++
class Solution {
public:
int largestRectangleArea(vector& heights){
int n=heights.size();
vector nsr(n,0);
vector nsl(n,0);
stack s;
for(int i=n-1;i >=0;i--){
while(!s.empty() && heights[i]<=heights[s.top()]){
s.pop();
}
if(s.empty()) nsr[i]=n;
else nsr[i]=s.top();
s.push(i);
}
while(!s.empty()) s.pop();
for(int i=0;i<n;i++){
while(!s.empty() && heights[i]<=heights[s.top()]){
s.pop();
}
if(s.empty()) nsl[i]=-1;
else nsl[i]=s.top();
s.push(i);
}
int ans=0;
for(int i=0;i<n;i++){
ans=max(ans, heights[i]*(nsr[i]-nsl[i]-1));
}
return ans;
}
};Java
class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
int[] nsr = new int[n];
int[] nsl = new int[n];
Stack s = new Stack<>();
for (int i = n - 1; i >= 0; i--) {
while (!s.isEmpty() && heights[i] <= heights[s.peek()]) {
s.pop();
}
if (s.isEmpty()) nsr[i] = n;
else nsr[i] = s.peek();
s.push(i);
}
while (!s.isEmpty()) s.pop();
for (int i = 0; i < n; i++) {
while (!s.isEmpty() && heights[i] <= heights[s.peek()]) {
s.pop();
}
if (s.isEmpty()) nsl[i] = -1;
else nsl[i] = s.peek();
s.push(i);
}
int ans = 0;
for (int i = 0; i < n; i++) {
ans = Math.max(ans, heights[i] * (nsr[i] - nsl[i] - 1));
}
return ans;
}
}
Python
class Solution(object):
def largestRectangleArea(self, heights):
n = len(heights)
nsr = [0] * n
nsl = [0] * n
s = []
for i in range(n - 1, -1, -1):
while s and heights[i] <= heights[s[-1]]:
s.pop()
if not s:
nsr[i] = n
else:
nsr[i] = s[-1]
s.append(i)
while s:
s.pop()
for i in range(n):
while s and heights[i] <= heights[s[-1]]:
s.pop()
if not s:
nsl[i] = -1
else:
nsl[i] = s[-1]
s.append(i)
ans = 0
for i in range(n):
ans = max(ans, heights[i] * (nsr[i] - nsl[i] - 1))
return ans
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment