Finding the Largest Area Rectangle In A Histogram

Histogram is nothing but a graphical representation of data using columns or bars of different heights. Histogram

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 Histogram_Stepwise


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> stack_of_height, stack_of_position;
    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.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
    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


Copyright (c) 2019-2021, Algotree.org.
All rights reserved.