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
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.
That is, consider the indices of starting and ending bars to be x
& y
respectively, then,
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.
Max rectangular area = [Min height bar (between x & y)] * [y – x + 1]
O(n^2)
, where n is the number of bars in the given Histogram.
import java.util.Scanner; public class maxHistogramArea { public static void main(String[] args) { Scanner scn = new Scanner(System.in); /*input number of bars in the histogram*/ int n = scn.nextInt(); long[] a = new long[n]; /*input height of each bar*/ for (int i = 0; i < a.length; i++) { a[i] = scn.nextLong(); } System.out.println(solve(a)); } public static long solve(long[] a) { /*final max rectangular area to be returned*/ long ans = 0; /*considering every bar as a starting point of an area*/ for (int i = 0; i < a.length; i++) { /*for keeping track of shortest bar encountered yet * when 'i' is chosen as the starting point of an area*/ long min = Integer.MAX_VALUE; /* area when when 'i' is chosen as the starting point * of an area*/ long rv=0; for (int j = i; j < a.length; j++) { /*current area will be the height of the shortest * bar multiplied with the number of bars*/ min = Math.min(min, a[j]); rv = Math.max(rv, min * (j - i+1)); } /*updating overall max with the current max*/ ans = Math.max(ans, rv); } return ans; } }
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 :
We can efficiently find the index of shortest bar in O(log n)
time with the help Range min Query using segment tree.
- 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.
O(n*log n).
import java.util.Scanner; public class maxHistogramArea { public static void main(String[] args) { Scanner scn = new Scanner(System.in); /* input number of bars in the histogram */ int n = scn.nextInt(); int[] a = new int[n]; /* input height of each bar */ for (int i = 0; i <a>ei) { return Integer.MIN_VALUE; } /*if there is only one bar, then the area will be * height of that bar, as width of each bar is one*/ if (si == ei) { return a[si]; } /*find index of the bar with minimum height*/ int minIdx = getQuery(0, 0, a.length-1, si, ei, a); /*recursive call to get maximum area from left of * this min height bar*/ int left = solve(si, minIdx - 1, a); /*recursive call to get maximum area from right of * this min height bar*/ int right = solve(minIdx + 1, ei, a); /* area calculation for whole of this current segment, * which is number of bars multiplied by height of the * shortest bar*/ int current = a[minIdx] * (ei - si + 1); /*max of all these areas will be the final result*/ return Math.max(current, Math.max(left, right)); } static int[] segArr; public static void SegInit(int[]arr) { int height = (int)(Math.ceil(Math.log(arr.length)/Math.log(2))); segArr = new int[(int)Math.pow(2,(height+1)) - 1]; construct(0, 0, arr.length-1, arr); } public static int construct(int saIdx, int left, int right, int[] arr) { /* * if the segment is of length one, then we know * it will be a left node and hence it will * contain an element of the given array */ if (left == right) { /* * element at the current index of segArr * will be the element present at index * left or right in given array, as left * is equal to right so we can take either * of them */ return segArr [saIdx] = left; } /* * current segment of parent node is divided * into two halves, if the segment for * parent is [left, right], then segment * for left child will be [left, mid] and * segment for right child will * be [mid+1, right]. */ int mid = (left + right) / 2; int leftChild = construct(2 * saIdx + 1, left, mid, arr); int rightChild = construct(2 * saIdx + 2, mid + 1, right, arr); /* * result of the current node will be calculated * in the post order after calculating * the result for its children */ segArr [saIdx] = arr [leftChild] > arr [rightChild] ? rightChild : leftChild; return segArr [saIdx]; } public static int getQuery(int saIdx, int left, int right, int ql, int qr, int[] arr) { // saIdx - pointer for the segment array. // left - left limit of the current segment. // right - right limit of the current segment. // ql - left limit of the given query segment. // qr - right limit of the given query segment. /* * if the range of the query lies completely outside * the range of the current segment, we return a * value which contributes nothing to the final answer, * that 0 in the case when sum is to be calculated * for given range. */ if (left > qr || right = ql && right arr [rightResult] ? rightResult : leftResult; } } } public static void update(int value, int idx, int saIdx, int left, int right, int[] arr) { /* * if the index lies outside the range of the current * segment then there is no need for an update/call * at that index, so simply return. */ if (idx right) { return; } /* * if we found the index to be updated, we update the * given array as well as the segment array that is * the node which has the segment equal to given index. */ if (idx == left && idx == right) { arr [left] = value; segArr [saIdx] = left; return; } /* * now in post order we need to update all the nodes * which contains the given index in their segment */ else { int mid = (left + right) / 2; update(value, idx, 2 * saIdx + 1, left, mid, arr); update(value, idx, 2 * saIdx + 2, mid + 1, right, arr); segArr [saIdx] = arr [segArr [2 * saIdx + 1]] > arr [segArr [2 * saIdx + 2]] ? segArr [2 * saIdx + 2] : segArr [2 * saIdx + 1]; } } }
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 takeO(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.
'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.
'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.
import java.util.Scanner; import java.util.Stack; public class maxHistogramArea { public static void main(String[] args) { Scanner scn = new Scanner(System.in); /* input number of bars in the histogram */ int n = scn.nextInt(); int[] a = new int[n]; /* input height of each bar */ for (int i = 0; i < a.length; i++) { a[i] = scn.nextInt(); } System.out.println(solve(a)); } public static int solve(int[] a) { Stack<Integer> stack = new Stack<>(); int maxArea = Integer.MIN_VALUE; for (int i = 0; i < a.length;) { /* this condition means that as the top element is * smaller than the incoming element, that is why, * it must not be popped and should be given more * time in stack as it can lead to a larger area later. * */ if (stack.isEmpty() || a[stack.peek()] <= a[i]) { stack.push(i); i++; } else { /*As the top of element is greater than the incoming * element, then this top element would no longer be * the smallest element in between 'i' th element and * previous element, hence, remove this, and calculate * area corresponding to this element */ int top = stack.pop(); if (stack.isEmpty()) { /*as no element is left in the stack this means * that this removed top element was the smallest * element in the array till 'i' th index*/ maxArea = Math.max(maxArea, a[top] * i); } else { /* area calculation for the removed top as the segment * for this element being the smallest has ended */ maxArea = Math.max(maxArea, a[top] * (i - stack.peek()-1)); } } } /* After 'i' has reached the end of the histogram array so * the upper loop will end, but we still have element left to * be processed in the stack, hence do the same process again * until stack becomes empty*/ while (!stack.isEmpty()) { int top = stack.pop(); if (stack.isEmpty()) { /*updating max rectangular area every time*/ maxArea = Math.max(maxArea, a[top] * a.length); } else { maxArea = Math.max(maxArea, a[top] * (a.length - stack.peek()-1)); } } return maxArea; } }
That’s all about Largest Rectangular Area in a Histogram.