Problem Statement: 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 histogram.
Example:
Input: N =6, heights[] = {2,1,5,6,2,3}
Output: 10
Explanation:
Solution
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Solution 1: Brute Force Approach
Intuition: The intuition behind the approach is taking different bars and finding the maximum width possible using the bar.
Similarly for other bars, we will find the areas possible:-
Considering the width of each bar as 1 unit.
For first bar, area possible = 2* 1 =2 sq . units
For second bar, area possible = 1 * 6 =6 sq . units
For third bar , area possible = 5 *2 = 10 sq . units
For fourth bar , area possible = 6 * 1 = 6 sq . units
For Fifth bar , area possible = 2 * 4 = 8 sq . units
For Sixth bar , area possible = 3 * 1 =3 sq . units
So, the maximum area possible = 10 sq units.
Approach:
The approach is to find the right smaller and left smaller element and find the largest Rectangle area in Histogram.
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
// Brute Force Approach to find largest rectangle area in Histogram
int largestarea(int arr[], int n) {
int maxArea = 0;
for (int i = 0; i < n; i++) {
int minHeight = INT_MAX;
for (int j = i; j < n; j++) {
minHeight = min(minHeight, arr[j]);
maxArea = max(maxArea, minHeight * (j - i + 1));
}
}
return maxArea;
}
int main() {
int arr[] = {2, 1, 5, 6, 2, 3, 1};
int n = 7;
cout << "The largest area in the histogram is " << largestarea(arr, n); // Printing the largest rectangle area
return 0;
}Output: The largest area in the histogram is 10
Time Complexity: O(N*N )
Space Complexity: O(1)
Java Code
import java.util.*;
// Brute Force Approach to find largest rectangle area in Histogram
public class Main {
static int largestarea(int arr[], int n) {
int maxArea = 0;
for (int i = 0; i < n; i++) {
int minHeight = Integer.MAX_VALUE;
for (int j = i; j < n; j++) {
minHeight = Math.min(minHeight, arr[j]);
maxArea = Math.max(maxArea, minHeight * (j - i + 1));
}
}
return maxArea;
}
public static void main(String args[]) {
int arr[] = {2, 1, 5, 6, 2, 3, 1};
int n = 7;
System.out.println("The largest area in the histogram is " + largestarea(arr, n)); // Printing the largest rectangle area
}
}Output: The largest area in the histogram is 10
Time Complexity: O(N*N )
Space Complexity: O(1)
Solution 2: Optimised Approach 1
Intuition: The intuition behind the approach is the same as finding the smaller element on both sides but in an optimized way using the concept of the next greater element and the next smaller element.
Approach:
- Steps to be done for finding Left smaller element
2. Steps to be done for finding the Right smaller element
After finding the right smaller and left smaller of each subsequent array elements, we
Area for first index – ( 0 – 0 +1 ) * 2 = 2
Area for second index – (6 – 0 + 1) * 1 = 6
Area for third index – (3 – 2 +1 ) * 5 = 10
Area for fourth index – (3 – 3 + 1 ) * 6 = 6
Area for fifth index – (5 – 2 +1 ) * 2 = 8
Area for sixth index – (5 – 5 + 1) * 3 = 3
Area for seventh index – (6 – 0 +1) * 1 = 7
So, the maximum area out of these is 10 sq units.
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int largestRectangleArea(vector < int > & heights) {
int n = heights.size();
stack < int > st;
int leftsmall[n], rightsmall[n];
for (int i = 0; i < n; i++) {
while (!st.empty() && heights[st.top()] >= heights[i]) {
st.pop();
}
if (st.empty())
leftsmall[i] = 0;
else
leftsmall[i] = st.top() + 1;
st.push(i);
}
// clear the stack to be re-used
while (!st.empty())
st.pop();
for (int i = n - 1; i >= 0; i--) {
while (!st.empty() && heights[st.top()] >= heights[i])
st.pop();
if (st.empty())
rightsmall[i] = n - 1;
else
rightsmall[i] = st.top() - 1;
st.push(i);
}
int maxA = 0;
for (int i = 0; i < n; i++) {
maxA = max(maxA, heights[i] * (rightsmall[i] - leftsmall[i] + 1));
}
return maxA;
}
};
int main() {
vector<int> heights = {2, 1, 5, 6, 2, 3, 1};
Solution obj;
cout << "The largest area in the histogram is " << obj.largestRectangleArea(heights);
return 0;
}Output: The largest area in the histogram is 10
Time Complexity: O( N )
Space Complexity: O(3N) where 3 is for the stack, left small array and a right small array
Java Code
import java.util.*;
// Brute Force Approach to find largest rectangle area in Histogram
public class Main {
public static int largestRectangleArea(int[] heights) {
int n = heights.length;
Stack < Integer > st = new Stack < > ();
int leftSmall[] = new int[n];
int rightSmall[] = new int[n];
for (int i = 0; i < n; i++) {
while (!st.isEmpty() && heights[st.peek()] >= heights[i]) {
st.pop();
}
if (st.isEmpty()) leftSmall[i] = 0;
else leftSmall[i] = st.peek() + 1;
st.push(i);
}
// clear the stack to be re-used
while (!st.isEmpty()) st.pop();
for (int i = n - 1; i >= 0; i--) {
while (!st.isEmpty() && heights[st.peek()] >= heights[i]) {
st.pop();
}
if (st.isEmpty()) rightSmall[i] = n - 1;
else rightSmall[i] = st.peek() - 1;
st.push(i);
}
int maxA = 0;
for (int i = 0; i < n; i++) {
maxA = Math.max(maxA, heights[i] * (rightSmall[i] - leftSmall[i] + 1));
}
return maxA;
}
public static void main(String args[]) {
int arr[] = {2, 1, 5, 6, 2, 3, 1};
int n = 7;
System.out.println("The largest area in the histogram is " +
largestRectangleArea(arr));
}
}Output: The largest area in the histogram is 10
Time Complexity: O( N )
Space Complexity: O(3N) where 3 is for the stack, left small array and a right small array
Solution 3: Optimised approach 2
Intuition:
This approach is a single pass approach instead of a two-pass approach. When we traverse the array by finding the next greater element, we found that some elements were inserted into the stack which signifies that after them the smallest element is themselves
So we can find the area of the rectangle by using arr[i] * (right smaller – left smaller -1 ).
Approach:
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int largestRectangleArea(vector < int > & histo) {
stack < int > st;
int maxA = 0;
int n = histo.size();
for (int i = 0; i <= n; i++) {
while (!st.empty() && (i == n || histo[st.top()] >= histo[i])) {
int height = histo[st.top()];
st.pop();
int width;
if (st.empty())
width = i;
else
width = i - st.top() - 1;
maxA = max(maxA, width * height);
}
st.push(i);
}
return maxA;
}
};
int main() {
vector < int > histo = {2, 1, 5, 6, 2, 3, 1};
Solution obj;
cout << "The largest area in the histogram is " << obj.largestRectangleArea(histo) << endl;
return 0;
}Output: The largest area in the histogram is 10
Time Complexity: O( N ) + O (N)
Space Complexity: O(N)
Java Code
import java.util.*;
public class TUF {
static int largestRectangleArea(int histo[]) {
Stack < Integer > st = new Stack < > ();
int maxA = 0;
int n = histo.length;
for (int i = 0; i <= n; i++) {
while (!st.empty() && (i == n || histo[st.peek()] >= histo[i])) {
int height = histo[st.peek()];
st.pop();
int width;
if (st.empty())
width = i;
else
width = i - st.peek() - 1;
maxA = Math.max(maxA, width * height);
}
st.push(i);
}
return maxA;
}
public static void main(String args[]) {
int histo[] = {3, 1, 5, 6, 2, 3};
System.out.println("The largest area in the histogram is " + largestRectangleArea(histo));
}
}Output: The largest area in the histogram is 10
Time Complexity: O( N ) + O (N)
Space Complexity: O(N)
Special thanks to Gurmeet Singh for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article