Finding the Largest Area Rectangle In A Histogram
Histogram is nothing but a graphical representation of data using columns or bars of different heights.
Largest Rectangle in Histogram 1 : 4 * 4 = 16 units. Largest Rectangle in Histogram 2 : 2 * 6 = 12 units.
Algorithm for finding the area of the largest rectangle in a histogram
1. For each bar do the following
a) If the height of the current bar is greater than the height of the previous bar, - Store the current bar’s height and the position in their respective stacks. Else if the height of the current bar is less than the height of the previous bar - Find the area of the largest rectangle that can be formed using the heights and the positions stored in the stack. - Pop-out the height and the position of each bar from the stack while calculating the area of the rectangle. - Continue finding the area using the heights stored in the stack that are greater than the current bar’s height. - Push the height of the current bar into the height stack and the position of the previously removed bar. 2. While the height stack is not empty - Find the area of the rectangle that can be formed using the histogram size, heights and the positions stored in the stack. - Pop-out the height and the position of each bar from the stack while calculating the area of the rectangle. - If the calculated area is greater than the earlier calculated areas, the largest rectangle is the newly found rectangle.
Consider the below example
Data structure used : Stack(s). One stack is used for storing the height and the other is used for storing the indices of the bars. Time Complexity : O(n), where n is the number of bars in histograms.
Program for finding the largest rectangle in the historgram
from collections import deque
def GetArea (histogram) :
sz = len(histogram)
stack_of_height = deque()
stack_of_position = deque()
area = 0
index = 0
height = 0
for pos in range(0, sz):
# If the height of the current bar is greater than the height
# at the top of stack push it.
if ( len(stack_of_height) == 0 or stack_of_height[0] <= histogram[pos] ) :
stack_of_height.appendleft(histogram[pos])
stack_of_position.appendleft(pos)
else :
if ( stack_of_height[0] > histogram[pos] ) :
# If the height of the current bar is less than the height at the top of
# the stack, pop out all the bigger heights and their corresponding positions
# and find the maximum area.
while ( len(stack_of_height) > 0 and stack_of_height[0] > histogram[pos] ) :
index = stack_of_position.popleft()
height = stack_of_height.popleft()
area = max(area, height * (pos-index))
# Note: We are pushing height of the current bar and the position of the last removed
# index.
stack_of_height.appendleft(histogram[pos])
stack_of_position.appendleft(index)
while ( len(stack_of_height) > 0 ) :
tempArea = stack_of_height[0] * (len(histogram) - stack_of_position[0])
stack_of_height.popleft()
stack_of_position.popleft()
if ( tempArea > area ) :
area = tempArea
return area
def main():
histogram_0 = [ 2, 3, 4, 5, 6, 4, 2, 1 ] # 16
histogram_1 = [ 6, 2, 5, 4, 5, 1, 6 ] # 12
histogram_2 = [ 6 ] # 6
histogram_3 = [ 7, 2, 1, 4, 5, 1, 3, 3 ] # 8
histogram_4 = [ 4, 1000, 1000, 1000, 1000 ] # 4000
histogram_5 = [ 1000, 1000, 1000, 1000 ] # 4000
histogram_6 = [ 2, 3, 4, 5, 5, 4, 3, 2 ] # 18
histogram_7 = [ 5, 5, 5, 5, 5 ] # 25
histogram_8 = [ 1, 1, 1, 1, 2, 2, 3 ] # 7
list_of_histograms = [ histogram_0, histogram_1, histogram_2, histogram_3, histogram_4, \
histogram_5, histogram_6, histogram_7, histogram_8]
for histogram in list_of_histograms:
print("Histogram : " + str(histogram) + " => Area : " + str(GetArea(histogram)))
if __name__ == "__main__":
main()
Output
Histogram : [2, 3, 4, 5, 6, 4, 2, 1] => Area : 16
Histogram : [6, 2, 5, 4, 5, 1, 6] => Area : 12
Histogram : [6] => Area : 6
Histogram : [7, 2, 1, 4, 5, 1, 3, 3] => Area : 8
Histogram : [4, 1000, 1000, 1000, 1000] => Area : 4000
Histogram : [1000, 1000, 1000, 1000] => Area : 4000
Histogram : [2, 3, 4, 5, 5, 4, 3, 2] => Area : 18
Histogram : [5, 5, 5, 5, 5] => Area : 25
Histogram : [1, 1, 1, 1, 2, 2, 3] => Area : 7
#include<iostream>
#include<stack>
#include<vector>
using namespace std;
typedef vector<int> VI;
typedef stack<int> SI;
int GetArea (vector<int> histogram) {
int sz = histogram.size();
stack<int> stk_height, stk_pos;
int area = 0;
int pos, height;
for (int pos=0; pos<sz; pos++) {
// If the height of the current bar is greater than the height
// at the top of stack push it.
if (stk_height.empty() || stk_height.top() <= histogram[pos]) {
stk_height.push(histogram[pos]);
stk_pos.push(pos);
} else {
// If the height of the current bar is less than the height at the top of
// the stack, pop out all the bigger heights and their corresponding positions
// and find the maximum area.
int index;
while (!stk_height.empty() && stk_height.top() > histogram[pos]) {
index = stk_pos.top();
stk_pos.pop();
height = stk_height.top();
stk_height.pop();
area = max(area, height * (pos-index));
}
// Note: We are pushing height of the current bar and the position of the last removed
// index.
stk_height.push(histogram[pos]);
stk_pos.push(index);
}
}
while (!stk_height.empty()) {
area = max(area, stk_height.top() * (sz - stk_pos.top()));
stk_height.pop();
stk_pos.pop();
}
return area;
}
int main() {
vector<int> vec0 = {2, 3, 4, 5, 6, 4, 2, 1}; // 16
vector<int> vec1 = {6, 2, 5, 4, 5, 1, 6}; // 12
vector<int> vec2 = {6}; // 6
vector<int> vec3 = {7, 2, 1, 4, 5, 1, 3, 3}; // 8
vector<int> vec4 = {4, 1000, 1000, 1000, 1000}; // 4000
vector<int> vec5 = { 1000, 1000, 1000, 1000}; // 4000
vector<int> vec6 = {2, 3, 4, 5, 5, 4, 3, 2}; // 18
vector<int> vec7 = {5, 5, 5, 5, 5}; // 25
vector<int> vec8 = {1, 1, 1, 1, 2, 2, 3}; // 7
vector<vector<int>> histogram_list = { vec0, vec1, vec2, vec3, vec4, vec5, vec6, vec7, vec8 };
for (auto histogram : histogram_list) {
cout << "Histogram : ";
for (auto num : histogram) {
cout << num << " ";
} cout << endl;
cout << "Area : " << GetArea(histogram) << endl;
}
return 0;
}
Output
Histogram : 2 3 4 5 6 4 2 1
Area : 16
Histogram : 6 2 5 4 5 1 6
Area : 12
Histogram : 6
Area : 6
Histogram : 7 2 1 4 5 1 3 3
Area : 8
Histogram : 4 1000 1000 1000 1000
Area : 4000
Histogram : 1000 1000 1000 1000
Area : 4000
Histogram : 2 3 4 5 5 4 3 2
Area : 18
Histogram : 5 5 5 5 5
Area : 25
Histogram : 1 1 1 1 2 2 3
Area : 7
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
class Histogram {
public int GetArea (List<Integer> histogram) {
int sz = histogram.size();
Stack<Integer> stack_of_height = new Stack<Integer>();
Stack<Integer> stack_of_position = new Stack<Integer>();
int area = 0;
int index = 0, height = 0;
for (int pos=0; pos<sz; pos++) {
// If the height of the current bar is greater than the height
// at the top of stack push it.
if ( stack_of_height.isEmpty() || stack_of_height.peek() <= histogram.get(pos) ) {
stack_of_height.push(histogram.get(pos));
stack_of_position.push(pos);
} else {
if ( stack_of_height.peek() > histogram.get(pos) ) {
// If the height of the current bar is less than the height at the top of
// the stack, pop out all the bigger heights and their corresponding positions
// and find the maximum area.
while ( !stack_of_height.isEmpty() && stack_of_height.peek() > histogram.get(pos) ) {
index = stack_of_position.pop();
height = stack_of_height.pop();
area = Math.max(area, height * (pos-index));
}
// Note: We are pushing height of the current bar and the position of the last removed
// index.
stack_of_height.push(histogram.get(pos));
stack_of_position.push(index);
}
}
}
while (!stack_of_height.isEmpty()) {
int tempArea = stack_of_height.peek() * (histogram.size() - stack_of_position.peek());
stack_of_height.pop();
stack_of_position.pop();
if (tempArea > area) {
area = tempArea;
}
}
return area;
}
public static void main (String args[]) {
Histogram h = new Histogram();
List<Integer> vec0 = Arrays.asList( 2, 3, 4, 5, 6, 4, 2, 1 ); // 16
List<Integer> vec1 = Arrays.asList( 6, 2, 5, 4, 5, 1, 6 ); // 12
List<Integer> vec2 = Arrays.asList( 6 ); // 6
List<Integer> vec3 = Arrays.asList( 7, 2, 1, 4, 5, 1, 3, 3 ); // 8
List<Integer> vec4 = Arrays.asList( 4, 1000, 1000, 1000, 1000 ); // 4000
List<Integer> vec5 = Arrays.asList( 1000, 1000, 1000, 1000 ); // 4000
List<Integer> vec6 = Arrays.asList( 2, 3, 4, 5, 5, 4, 3, 2 ); // 18
List<Integer> vec7 = Arrays.asList( 5, 5, 5, 5, 5 ); // 25
List<Integer> vec8 = Arrays.asList( 1, 1, 1, 1, 2, 2, 3 ); //7
List<List<Integer>> histogram_list = Arrays.asList(vec0, vec1, vec2, vec3, vec4, vec5, vec6, vec7, vec8);
for (List<Integer> histogram : histogram_list) {
System.out.print("Histogram : ");
for (Integer num : histogram) {
System.out.print(num + " ");
} System.out.println();
System.out.println("Area : " + h.GetArea(histogram));
}
}
}
Output
Histogram : 2 3 4 5 6 4 2 1
Area : 16
Histogram : 6 2 5 4 5 1 6
Area : 12
Histogram : 6
Area : 6
Histogram : 7 2 1 4 5 1 3 3
Area : 8
Histogram : 4 1000 1000 1000 1000
Area : 4000
Histogram : 1000 1000 1000 1000
Area : 4000
Histogram : 2 3 4 5 5 4 3 2
Area : 18
Histogram : 5 5 5 5 5
Area : 25
Histogram : 1 1 1 1 2 2 3
Area : 7