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. 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 = 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


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