Largest Rectangular Area in a Histogram

If you want to practice data structure and algorithm programs, you can go through Java coding interview questions.

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 Structures in java 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.

  • Now, if stack becomes empty, then area = top * i
  • else,area = top * (i - stack.peek() - 1).

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.

Related Posts

  • Maximum number of vowels in a Substring of given length
    18 June

    Maximum Number of Vowels in a Substring of Given Length

    Table of ContentsApproach – 1 Generate All Substrings Using substring() MethodApproach – 2 Using Sliding Window Method (Linear Time Solution) In this article, we will look at an interesting problem related to the Strings and [Sliding-Window Algorithm](https://java2blog.com/sliding-window-maximum-java/ “Sliding-Window Algorithm”). The problem is : "Given a String we have to Find the Maximum Number of Vowel […]

  • Find first and last position of element in sorted array
    04 June

    Search for a range Leetcode – Find first and last position of element in sorted array

    Table of ContentsApproach 1 (Using Linear Search)Approach 2 (Using Modified Binary Search-Optimal) In this article, we will look into an interesting problem asked in Coding Interviews related to Searching Algorithms. The problem is: Given a Sorted Array, we need to find the first and last position of an element in Sorted array. This problem is […]

  • 30 April

    Convert Postfix to Infix in Java

    Learn about how to convert Postfix to Infix in java.

  • Prefix to postfix in java
    30 April

    Convert Prefix to Postfix in Java

    Learn about how to convert Prefix to Postfix in java.

  • Data structures in java
    16 April

    Data Structures in java

    Table of ContentsArray Declare and initialize array in javaAdvantages of arrayDisadvantages of array ExampleArray practice programsStackStack implementation using ArrayStack implementation using LinkedListImplementationPractice ProgramsQueueQueue implementation using arrayQueue implementation using LinkedListImplementationLinkedListImplementationLinkedList Practice ProgramsBinary treeImplementationBinary tree practice programsBinary Search treeImplementationBinary search tree Practice programsTrieImplementationHeapImplementationGraphImplementation Inbuild data structures in javaStringHashMapLinkedHashMapArrayListLinkedListHashSet In this post, we will see about various data […]

  • 29 November

    Top 100+ Java coding interview questions

    Table of ContentsStringQuestion 1 : How to reverse a String in java? Can you write a program without using any java inbuilt methods?Question 2 : Write a java program to check if two Strings are anagram in java?Question 3 : Write a program to check if String has all unique characters in java?Question 4 : […]

Leave a Reply

Your email address will not be published. Required fields are marked *

Subscribe to our newletter

Get quality tutorials to your inbox. Subscribe now.