Last Updated: 7 Jan, 2021
Largest cake
Moderate
Asked in companies
Ram on his birthday ordered a cake which is in the shape of a histogram such that cake is divided into ‘N’ bars and each bar width equal to one. The height of each bar is known.
Since it’s his birthday, so he wants to eat the maximum of the cake, but he can have the cake only once and in rectangle shape. Help him find the area of the largest rectangle in the cake.
You will be given an array/list 'CAKE' of ‘N’ non-negative integers representing the cake's bar height where the width of each bar is one. You have to find the area of the largest rectangle in the cake.
Example:
For given array = {3,1,7,8,1,2}
Above is the cake in the shape of a histogram where the width of each bar is 1, given array cake = {3,1,7,8,1,2}, the largest rectangle is shown with red outline having an area of 7 * 2 = 14 units.
Input format :
The first line of input contains an integer ‘T’ denoting the number of test cases.
The next 2 * 'T’ lines represent the ‘T’ test cases.
The first line of each test case contains a single integer 'N' denoting the size of the array.
The second line of each test case contains 'N' space-separated integers denoting the array elements.
Output format :
For each test case, return a single integer representing the largest area of the rectangle in the histogram.
Note:
You don’t have to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= N <= 10^4
0 <= CAKE[I] <= 10^5
Where ‘CAKE[I]’ is the value at index 'i' of the array 'CAKE'.
Time limit: 1 sec
Approaches
The idea is to check all the possible combinations by taking every bar as a starting point of an area. So we will consider each bar one by one as the starting point, consider every bar is having an index greater than the index of the starting bar to calculate the area between them, and after calculating the area with every starting point, we update the maximum possible rectangular area and finally return it after all starting points are checked.
The steps are as follows:
- Initialize the ‘RESULT’ to zero.
- Now run the two loops outer one starting from index ‘i’ = 0 to the end of the array, and this loop is choosing each bar as a starting point and initialize ‘HEIGHT’ = MAX_VALUE; for every iteration. This variable will store the height of the shortest bar and initialize the 'CURRAREA' = 0.
- Now for the inner loop, start from index ‘j’ = ‘i’ till the end of the array. Now inside this loop, you will be calculating the area for each considered rectangle.
- ‘CURRAREA’ = MATH.MAX('CURRAREA','CURR' * ('j' - ‘i’ +1)).
- Now outside this loop update the ‘RESULT’ = MATH.MAX('RESULT', 'CURRAREA').
- Now finally, return the ‘RESULT’.
As in the previous approach, we have seen that calculating the maximum area of the rectangle in any possible combination depends on the bar with smaller height but considering every combination was costing us more time complexity so to reduce this, we will be using stack. Now the question arises what we will store in the stack so the answer to this we will be storing the indices of the elements in decreasing order of heights that means we will be storing indexes of smaller height on top and of bigger heights below, therefore element on the top, index of the nearest and smallest element to the left of it will be below it and for right it will be the next element in the iteration. So will calculate the area with the help of this top element now.
The steps are as follows:
- Initialize the ‘RESULT’ = 0.
- Run a loop starting from index ‘i’ = 0 till the end of the array, now inside this loop.
- Check the condition for the stack as we want to push the elements in decreasing order, so we will use the current index on top is smaller than the incoming element, so we will write if('CAKE[STACK.PEEK()]' <= ‘CAKE[i]’) and if the condition satisfies we will push the index of the current element to the stack top.
- If the condition fails, then the incoming element is smaller, so we need to pop the top element, and we need to calculate the area till this point so let ‘J’ = ‘STACK.POP()’, therefore ‘RESULT’ = MATH.MAX('RESULT', ('i' - ‘STACK.PEEK()’ - 1) * ‘CAKE[J]'.
- After the process of all the elements, we will have to check that whether the ‘STACK’ is empty or not, so will we will be iterating the stack till it is empty and repeat the same process as above to calculate the area.
- Finally, return ‘RESULT’.
Similar problems