# Area of largest rectangle in Histogram

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:

1. 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)