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 of finding the largest rectangle in the historgram. 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.

Python

Python : Finding the largest rectangle in the historgram.

C++

C++ Finding the largest rectangle in the historgram.

Java: Finding the largest rectangle in the historgram.

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.