Largest Rectangle In Histogram
Finding the largest rectangle in 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 = 1
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
print("Histogram [2, 3, 4, 5, 6, 4, 2, 1] : " + str(GetArea(histogram_0)))
histogram_1 = [ 6, 2, 5, 4, 5, 1, 6 ] # 12
print("Histogram [6, 2, 5, 4, 5, 1, 6] : " + str(GetArea(histogram_1)))
histogram_2 = [ 6 ] # 6
print("Histogram [ 6 ] : " + str(GetArea(histogram_2)))
histogram_3 = [ 7, 2, 1, 4, 5, 1, 3, 3 ] # 8
print("Histogram [ 7, 2, 1, 4, 5, 1, 3, 3 ] : " + str(GetArea(histogram_3)))
histogram_4 = [ 4, 1000, 1000, 1000, 1000 ] # 4000
print("Histogram [ 4, 1000, 1000, 1000, 1000 ] : " + str(GetArea(histogram_4)))
histogram_5 = [ 1000, 1000, 1000, 1000 ] # 4000
print("Histogram [ 1000, 1000, 1000, 1000 ] : " + str(GetArea(histogram_5)))
histogram_6 = [ 2, 3, 4, 5, 5, 4, 3, 2 ] # 18
print("Histogram [ 2, 3, 4, 5, 5, 4, 3, 2 ] : " + str(GetArea(histogram_6)))
histogram_7 = [ 5, 5, 5, 5, 5 ] # 25
print("Histogram [ 5, 5, 5, 5, 5 ] : " + str(GetArea(histogram_7)))
if __name__ == "__main__":
main()
Output
Histogram {2, 3, 4, 5, 6, 4, 2, 1} : 16
Histogram {6, 2, 5, 4, 5, 1, 6} : 12
Histogram {6} : 6
Histogram {7, 2, 1, 4, 5, 1, 3, 3} : 8
Histogram {4, 1000, 1000, 1000, 1000} : 4000
Histogram { 1000, 1000, 1000, 1000} : 4000
Histogram {2, 3, 4, 5, 5, 4, 3, 2} : 18
Histogram {5, 5, 5, 5, 5} : 25
#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> stack_of_height, stack_of_position;
int area = 0;
int index = 0, height = 1;
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.empty() || stack_of_height.top() < histogram[pos] ) {
stack_of_height.push(histogram[pos]);
stack_of_position.push(pos);
} else {
if ( stack_of_height.top() > 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 ( !stack_of_height.empty() && stack_of_height.top() > histogram[pos] ) {
index = stack_of_position.top();
stack_of_position.pop();
height = stack_of_height.top();
stack_of_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.
stack_of_height.push(histogram[pos]);
stack_of_position.push(index);
}
}
}
while (!stack_of_height.empty()) {
int tempArea = stack_of_height.top() * (histogram.size() - stack_of_position.top());
stack_of_height.pop();
stack_of_position.pop();
if (tempArea > area) {
area = tempArea;
}
}
return area;
}
int main(){
vector<int> vec0 = {2, 3, 4, 5, 6, 4, 2, 1}; // 16
cout << "Histogram {2, 3, 4, 5, 6, 4, 2, 1} : " << GetArea(vec0) << endl;
vector<int> vec1 = {6, 2, 5, 4, 5, 1, 6}; // 12
cout << "Histogram {6, 2, 5, 4, 5, 1, 6} : " << GetArea(vec1) << endl;
vector<int> vec2 = {6}; // 6
cout << "Histogram {6} : " << GetArea(vec2) << endl;
vector<int> vec3 = {7, 2, 1, 4, 5, 1, 3, 3}; // 8
cout << "Histogram {7, 2, 1, 4, 5, 1, 3, 3} : " << GetArea(vec3) << endl;
vector<int> vec4 = {4, 1000, 1000, 1000, 1000}; // 4000
cout << "Histogram {4, 1000, 1000, 1000, 1000} : " << GetArea(vec4) << endl;
vector<int> vec5 = { 1000, 1000, 1000, 1000}; // 4000
cout << "Histogram { 1000, 1000, 1000, 1000} : " << GetArea(vec5) << endl;
vector<int> vec6 = {2, 3, 4, 5, 5, 4, 3, 2}; // 18
cout << "Histogram {2, 3, 4, 5, 5, 4, 3, 2} : " << GetArea(vec6) << endl;
vector<int> vec7 = {5, 5, 5, 5, 5}; // 25
cout << "Histogram {5, 5, 5, 5, 5} : " << GetArea(vec7) << endl;
return 0;
}
Output
Histogram {2, 3, 4, 5, 6, 4, 2, 1} : 16
Histogram {6, 2, 5, 4, 5, 1, 6} : 12
Histogram {6} : 6
Histogram {7, 2, 1, 4, 5, 1, 3, 3} : 8
Histogram {4, 1000, 1000, 1000, 1000} : 4000
Histogram { 1000, 1000, 1000, 1000} : 4000
Histogram {2, 3, 4, 5, 5, 4, 3, 2} : 18
Histogram {5, 5, 5, 5, 5} : 25
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 = 1;
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
System.out.println( "Histogram (2, 3, 4, 5, 6, 4, 2, 1} : " + h.GetArea(vec0));
List<Integer> vec1 = Arrays.asList( 6, 2, 5, 4, 5, 1, 6 ); // 12
System.out.println("Histogram (6, 2, 5, 4, 5, 1, 6} : " + h.GetArea(vec1));
List<Integer> vec2 = Arrays.asList( 6 ); // 6
System.out.println("Histogram ( 6 ) : " + h.GetArea(vec2));
List<Integer> vec3 = Arrays.asList( 7, 2, 1, 4, 5, 1, 3, 3 ); // 8
System.out.println("Histogram (7, 2, 1, 4, 5, 1, 3, 3) : " + h.GetArea(vec3));
List<Integer> vec4 = Arrays.asList( 4, 1000, 1000, 1000, 1000 ); // 4000
System.out.println("Histogram ( 4, 1000, 1000, 1000, 1000 ) : " + h.GetArea(vec4));
List<Integer> vec5 = Arrays.asList( 1000, 1000, 1000, 1000 ); // 4000
System.out.println("Histogram ( 1000, 1000, 1000, 1000 ) : " + h.GetArea(vec5));
List<Integer> vec6 = Arrays.asList( 2, 3, 4, 5, 5, 4, 3, 2 ); // 18
System.out.println("Histogram ( 2, 3, 4, 5, 5, 4, 3, 2 ) : " + h.GetArea(vec6));
List<Integer> vec7 = Arrays.asList( 5, 5, 5, 5, 5 ); // 25
System.out.println("Histogram ( 5, 5, 5, 5, 5 ) : " + h.GetArea(vec7));
}
}
Output
Histogram (2, 3, 4, 5, 6, 4, 2, 1} : 16
Histogram (6, 2, 5, 4, 5, 1, 6} : 12
Histogram ( 6 ) : 6
Histogram (7, 2, 1, 4, 5, 1, 3, 3) : 8
Histogram ( 4, 1000, 1000, 1000, 1000 ) : 4000
Histogram ( 1000, 1000, 1000, 1000 ) : 4000
Histogram ( 2, 3, 4, 5, 5, 4, 3, 2 ) : 18
Histogram ( 5, 5, 5, 5, 5 ) : 25