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,
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
package Algos; 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 :
(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).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 |
package Algos; 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]; } } } </a> |
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
histogramwould 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.
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
package Algos; 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.
