Largest Rectangular Area in a Histogram

Previous
Next

In this post, we will see about how to find largest rectangular area in a Histogram.


Problem

Given an Integer representing number of bars in a Histogram and an array of integers representing the height of the bars in the given Histogram. Find the maximum Rectangular area possible in the Histogram given when the width of each bar is considered to be one unit.

For example, Consider the histogram given below,

INPUT :
8
3 1 6 4 3 2 1 5
OUTPUT :
9

Solution

APPROACH – I :

A very basic approach can be, considering every bar as a starting point of area.
We can one by one consider each bar as the starting point of area and then for each starting point consider every bar having index greater than the index of the starting bar to calculate area between them.
After calculation of area with every starting point we update the maximum possible rectangular area and finally return it after al starting points are exhausted.

Now, the maximum rectangular area between any two bars in a Histogram can be calculated by multiplying the number of bars in between starting bar and ending bar (both inclusive) by the height of the shortest bar.
This is because it is given, width of every bar is one.
That is, consider the indices of starting and ending bars to be ‘x’ & ‘y’ respectively, then,

Max rectangular area = [Min height bar (between x & y)] * [y – x + 1]

Time complexity Discussion :
As each bar is considered as starting point and for every starting point we are considering all bars as ending points (obviously with ending index greater than starting index) which clearly gives the idea of the worst time complexity of the order O(n^2), where n is the number of bars in the given Histogram.

APPROACH – II (RECURSIVE):

This problem can be solved recursively using Divide and Conquer technique in which we divide the problem into two parts, that is, we divide the area to work with in array into two independent problems, whose result can be combined to give the result of bigger problem.

Now the point of division of any problem into two subproblems will be the index of the bar with minimum height in that particular area of the array of any current problem and not the complete array (just like in all other Divide and conquer approaches for example in mergesort and quicksort).

Now the maximum area for the current problem will be the maximum of :
(i) Current Maximum area including all the bars : This will be the maximum possible rectangular area in the current subproblem which will be calculated by Multiplying the height of the shortest bar with the Number of bars in a particular area (current subproblem).
(ii) Maximum possible rectangular area on the left side of the minimum height bar which will be calculated recursively.
(iii) Maximum possible rectangular area on the right side of the minimum height bar which will also be calculated recursively.

We can efficiently find the index of shortest bar in O(log n) time with the help Range min Query using segment tree.

Algorithm :
Step – I :
Find the index of the bar with minimum height.
Step – II :

  • Recursive call for finding the maximum rectangular area in left side of this minimum index.
  • Recursive call for finding the maximum rectangular area in right side of this minimum index.
  • calculation of maximum rectangular area in the current segment.

STEP – III :
Return Maximum of all of the three calculated areas.

Time complexity Discussion :
At every step, we are dividing the subarray into two parts where the separation point is the minimum height bar which is getting calculated using Range min query in Segment tree. Now, in the worst case if the array is sorted in ascending/ descending order, then the division would be, one element in one side and (n-1) elements on other side which will lead to total ‘n’ divisions and at every step finding min index in O(log n) leading to a worst time complexity of O(n*log n).

Approach – III (ITERATIVE) :

As we know, calculation of maximum rectangular area in any segment of the histogram depends upon the shortest bar in that area (if we include all of the bars), hence,

  • This problem can be solved more efficiently if we calculate area for every bar when being the shortest in its rectangle for which we need to know the index of closest smaller bar on left and the index of closest smaller bar on right. Calculation of these indices for every element in the given histogram would take O(n^2) time which makes it even more inefficient.
  • But this task can be done in linear time usingĀ Stack data structure in which basically heights are stored in non-increasing order. This stack does not actually stores the height of the bars but instead stores their indices.
  • For any element on top of the stack, index of closest smaller bar on left will be the element just below the top element and index of closest smaller bar on right will be the next incoming element which is to be pushed.

The stack is maintained such that for any ‘i’th element, top of the stack is the index of the shortest bar between the previous stack element (element just below top) and ‘i’th element excluding this ‘i’th and element just below top.
Now as top is the smallest element till now, therefore, we can easily calculate area by multiplying this top element height with the number of elements BETWEEN ‘i’ and index just below top (lets call this as previous index). that is,

area = top * (i – previous index – 1)

Algorithm :

(i) If stack is empty or element on top is smaller than the current incoming element then, push the element straightaway without popping (as the top element will still be the smallest between previous index and i) and increment the index i.

(ii) if top of the stack is greater than the incoming element, then this means that the top element is no longer the smallest element in the current segment, and hence, pop the top element from stack.
<ul><li> Now, if stack becomes empty, then area = top * i
<li>else,area = top * (i – stack.peek() – 1).</li></ul>
There will not be any increment in index i as this element is yet to be pushed into the stack.

(iii) Follow the above steps until index i reached the end of the array.

(iv) Now, after index i has reached the end, there might be a possibility that still there are elements left in the stack to be processed, that is why, we follow the above steps until the stack becomes empty.

Time complexity if this approach is O(n) as every element is getting pushed and popped not more than one time.

That’s all about Largest Rectangular Area in a Histogram.

Previous
Next

Add Comment