Kata

Give in input an array representing the heights of each bar of a histogram, find the maximum area within it.

The following image explain it better than any word:

Hint: Use Stack: Here a small description that explain how to use:

1. As we traverse the heights array we will compare the height so far seen

(stored on the top of stack -corresponding to the index of the height input array) if it smaller in value with the current element in heights array, we will push the index of the height array , because at latter point of time it may lead to maximum area due to increase in height.

for example if height array is :{2,3,3,5,2} current stack contains only [{2}] here area that will be maximum is due to 3*1=3. (3=height of histogram and width is 1).

After this stack contain will be [{2,3}]

2. Otherwise, we will check if it is equal to the current top element on the stack, if so we will continue with next height in the array, it's because this will be considered later for area calculation , and moreover we had not traversed the entire array so we cannot assume anything now.

for example if height array is :{2,3,3,5,2} current stack contains only [{2,3}]here area that will be maximum is due to 3*2=6, if we consider 3 as next element, but it may possible that 3 can also be seen in future, so we will just ignore it to as it is already in the stack,it will be considered for area caculation if we find anyting in future which will be smaller than this height {3} , as it will break the rectangle property at that future height. After this stack will contain [{2,3}]

than we will go to step 1, as 5 is the next element, so which is greater in value than the top of the stack, so we will push it [{2,3,5}]- stack content after 5 is processed.

3. if however height in the array is smaller than at the top of stack, than we must pop all elements till we have height at the top of stack is smaller than the current height or stack becomes empty, as this height in the array will break the rectangle property which was maintained by the top of the stack element.

for example, so when we will be processing last element at the stack which is 2, 5 should be popped out, as height 2 will not be able to complete the rectangular height of 5. an we will continue this process till we found element at the top of the stack which is equal to or smaller in value, than the current height.

By the above process, we will pop element 3 element also and it will contribute area of 3*3(width)=9. After thisstack content will be [{2}].

4. if no more heights to process we will process the remaining element on the stack.

by that we will get the maximum area as 2*5(width)=10.