Question

8. Provide an O(n log n) time divide-and-conquer algorithm to find the area of the largest area rectangular region that lies entirely within a given histogram. The histogram consists of bars of width one that extend upwards from the x-axis. Bar i extends upward from the line y 0 to the line y topi) For example in the following histogram with 8 bars, the area of the largest rect- angular region that lies entirely within the histogram with tops (8,5,6,9,2,5,4,5) is 20. e histogram with tops (3,5,6,9,2,5,

Answer 1

This problem can be solved in time by using a divide and conquer algorithm. The key idea behind this is, we need to find the lowest value of a bar of the given histogram. And then, the maximum area of the rectangle will be equal to either of the following cases:

null

• maximum area on the left of the given bar
• maximum area on the right of the given bar
• the product of the number of bars altogether and the lowest value of the bar

We can find out the areas on the right and left using a recursion.

Now let's come to the implementation of the algorithm. I am providing you with a pseudocode.

maximumAreaOfRectangle(h[]):{
define minValueOfBar(h,i,j):
{ if (h[i]<h[j]) {return i}
else {return j}}
define getMid(a,b){
return a+((b-a)/2)}
define findIndexOfMinimumValueFromRange(h, st, ss, se, qs, qe, index){
if (qs<=ss && qe>=se){
return segment[index]}
else if (se<qs || ss>qe)
return -1
mid = getMid(ss,se)
return minValueofBar(h, findIndexOfMinimumValueFromRange(h, st, ss, mid, qs, qe, 2*index+1), findIndexOfMinimumValueFromRange(h, st, mid+1, se, qs, qe, 2*index+2))}
define IndexOfMinimumValue(h, st, n, qs, qe){
return findIndexOfMinimumValueFromRange(h, st, 0, n-1, qs, qe, 0)}
define constructSegmentTree(h, ss, se, st, si){
if (ss==se){
st[si]=ss
return ss}
else{
mid=getMid(ss,se)
st[si]=minValueOfBar(h, constructSegmentTree(h, ss, mid, st, (2*si)+1), constructSegmentTree(h, mid+1, se, st, (2*si)+2))
return st[si]}
define segmentTree(h,n){
maxSize=2*(2^ceil(ln n))-1
st=maxSize
constructSegmentTree(h, 0, n-1, st,0)
return st}
define getMaxAreaRectangle(h, st, n, l, r){
if (l==r) {return h[l]}
else {
m = IndexOfMinimumValue(h, st, n, l, r)
return max((getMaxAreaRectangle(h, st, n, l, m-1), getMaxAreaRectangle(h, st, n, m+1, r), (r-l+1)*h[m])}
define maxArea(h, n){
st=segmentTree(h,n)
return getMaxAreaRectangle(h, st, n, 0, n-1)}
return maxArea(h, len(h)}

So, to understand how this code works, let me explain to you what each function does.

• The first function defined minValueOfBar computes the minimum of two numbers in the histogram.
• The getMid function gets the middle index if the corner indices are provided as arguements.
• The findIndexOfMinimumValueFromRange function is a recursive function to get the index of the minimum value in a given range of indices. It takes the parameters h (the histogram), st (pointer to the segment tree), index (index of current node), ss and se (the starting and ending of the segment of current nodes) qs and qe (the starting and ending indices of query range).
• The IndexOfMinimumValue returns minimum element in range from qs to qe.
• The constructSegmentTree constructs segment tree st from index ss to se.
• The segmentTree constructs the tree from a given array.
• The getMaxAreaRectangle finds maximum rectangular area from segment tree.
• The maxArea function finally computes the area.

The time taken to compute the area is equal to the sum of the time to build the segment tree and to recursively find the area. The segment tree will be built in time. Let the time required to find the area recursively be T(n).
so T(n)=
null
.

So, the overall time is which is
null
.