Largest cake

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
4 upvotes
Asked in companies
OlaInspirisys

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
6
3 1 7 8 1 2
3
1 2 4
Sample Output 1 :
14
4
Explanation of The Sample Output 1:
In test case 1, It is explained in the discussion, and the maximum area will be 14 units. 

In test case 2, Array elements are 1,2,4. So the histogram will be: 


And the maximum area is marked with red, and that is 2 * 2 = 4 units.
Sample Input 2 :
2
3
3 2 1
4
1 9 8 4
Sample Output 2 :
4
16
Explanation of The Sample Output 2:
In test case 1, The array elements are 3,2 and 1, so the histogram will be:


We can clearly see that the rectangle with maximum area is marked with red having an area of 4 units.

In test case 2, Array elements are 1, 9, 8, 4. So  the maximum area will be by bars with height 8 and 9, with total width of 3 and thus maximum area will be 8 * 2 = 16 units.
Hint

Try to consider all possible pairs.

Approaches (2)
Brute Force

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’.
Time Complexity

O(N^2), Where ‘N’ denotes the number of elements in the Array.

 

Since we are using two nested loops of length N each and thus the time complexity will be O(N^2).

Space Complexity

O(1)

 

Since we are using constant space and thus the space complexity will be O(1).

Code Solution
(100% EXP penalty)
Largest cake
Full screen
Console