Largest Rectangular Area in a given Histogram

Given a histogram find the largest rectangle (rectangular area) that can be made out of the number of contiguous bars, assuming that every bar has the same width and that is 1.

For example, consider a histogram with 7 bars (as shown in the figure) of heights {6, 2, 6, 5, 6, 5, 1, 7}. The largest possible rectangle area is 20.

The naive solution is to one by one consider all bars and calculate the area of all rectangles starting with every bar and finally, return a maximum of all possible areas. The time complexity of this solution would be O(n^2).

Optimized Solutions – The algorithm to find the largest rectangular area in a histogram can be made to run in O(N) time if instead of using a naive solution, we use the following approach.

1. Create an empty stack.
2. Start from the first bar, and repeat step 3 & step 4 for every hist[i] where ‘i’ lies in range 0 to n-1.
3. If the stack is empty or element at index i is less than the top of the stack, then push i into the sack and increment i to point to next element.
4. Else, if the condition at step 3 is false, then pop the index stored at the top of the stack, store it in variable let’s say the top and check for one among this two condition-
   1. if the stack is empty then current_area = arr[top]*i, and if current_area> max_area, max_area = arr[top]*i
   2. if the stack if not empty, then this means, we have all the (indexes of)elements in the stack, that is greater than the number at index i, so, we will keep popping the element until we will reach the element which would be less than our element at index i, and every time we pop, we will do current_area = arr[top]*(i – stack.top() – 1), and again if current_area> max_area, max_area = arr[top]*i
5. If the stack is not empty, then one by one remove all elements from the stack and perform step 4.2 for every removed element.

Implementation of the above algorithm

// CPP program to find maximum rectangular
// area in a give histogram in linear time  

#include <bits/stdc++.h>
using namespace std;

//fucntion to calculate the maximum possible area
int find_area(int *arr, int n)
{
	int i=0, max_area = 0, area = 0;

	//create an empty stack to hold the 
	//indexes for array
	stack<int> st;

	while(i<n)
	{
		//if stack is empty of the current element
		//to be inserted is less the element at the 
		//top of the stack, push the curretn element
		//into the stack
		if(st.empty() || arr[st.top()] < arr[i])
		{
			st.push(i++);
		}
		else{

			//stores the index at TOS
			int top = st.top();
			st.pop(); //pop the TOS

			//calulate the maximum possible area for a given bar
			area = arr[top]*(st.empty()? i : i-st.top()-1);

			//update is current area is greater than the maximum
			//area then update the maximum area
			max_area = max(max_area, area);
		}

	}

	// Pop the remaining bars from stack and calculate 
    // area with every bar
	while(!st.empty())
	{
		int top = st.top();
		st.pop();

		area = arr[top]*(st.empty()? i : i-st.top()-1);

		max_area = max(max_area, area);

	}

	return max_area;
}

// Execution starts from here
int main()
{
	int hist[] = {6,2,6,5,6,5,1,7};
	int n = sizeof(hist)/sizeof(hist[0]);

	cout<<"Maxium rectangular area is = "find_area(hist, n)<<endl;

	return 0;
}

Output
Maxium rectangular area is = 20

Time Complexity

The time complexity of this optimized implementation will be O(N) because we are basically traversing all the entire list of N elements exactly once. The stack operation such as push, pop, top, etc is going to take constant time.