Piles of Boxes

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
2 upvotes

Problem statement

You are given 'N' piles of boxes. The heights of each pile are given by an array named 'HEIGHTS'. You hired a worker to shift these piles of boxes from your old house to your new house. But the worker will take the job only if the heights of each pile are the same as the pile with minimum height. In one step, you can lower the height of the tallest pile only to the next taller pile.

Find the number of steps required to make the height of each pile the same as the pile with minimum height.

Note: You can change the height of only one pile at once, even if there are multiple piles with the same height.

Example: 
Input: ‘N’ = 3,  ‘HEIGHTS’ = [2, 3, 6] 

Output: 3

Step 1 = [2, 3, 3],
Step 2 = [2, 3, 2],
Step 3 = [2, 2, 2].
Hence, the total number of steps required is 3.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line will contain the integer 'T', denoting the number of test cases.

The first line of each test case contains an integer ‘N’ denoting the length of the array ‘HEIGHTS’.

The second line of each test case contains ‘N’ integers denoting the heights of the piles of boxes.
Output format : 
For each test case, return the number of steps required to bring the height of the entire pile to the same height as the pile with minimum height.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 10^5
1 <= A[i] <= 10^5

Time Limit: 1 sec
Sample Input 1 :
2
4
4 9 2 6
2
1 2
Sample Output 1 :
6
1
Explanation Of Sample Input 1 :
For the first case:
1st step convert 9 to 6 then ‘HEIGHTS’ = [4, 6, 2, 6]
2nd step convert 6 to 4 then ‘HEIGHTS’ = [4, 4, 2, 6]
3rd step convert 6 to 4 then ‘HEIGHTS’ = [4, 4, 2, 4]
4th step convert  4 to 2 then ‘HEIGHTS’ = [2, 4, 2, 4]
5th step convert 4 to 2 then ‘HEIGHTS’ = [2, 2, 2, 4]
6th step convert 4 to 2 then ‘HEIGHTS’ = [2, 2, 2, 2]
Hence, the total steps required is 6.    

For the second case:
In one step, convert 2 to 1 then  'HEIGHTS' = [1, 1]. So the total steps required is 1.
Sample Input 2 :
2
6
20 12 1 28 16 20 
5
2 14 29 21 11
Sample Output 2 :
13
10
Hint

Can you think about a straightforward solution using a max heap?

Approaches (2)
Brute Force

In the naive approach, First, we push the height of each pile into the max heap. The top of the max heap contains the pile with the maximum height. We will extract all the piles from the max heap with a height equal to the maximum height and store them in an array ‘ALLCURMAX’. Then we will change the height of all the piles in ‘ALLCURMAX’ from maximum height to the next maximum height and then push them back into the max heap. Let the number of piles with maximum height be ‘X.’ Then we increment the total number of steps by ‘X’ because we need to change the height one by one. We will keep doing it iteratively unless all the piles in the max heap have the same height.


 

The steps are as follows:-

Function  getTotalSteps(vector<int>& heights):

  1. Declare a max_heap.
  2. Push each pile into the max_heap.
  3. Declare a variable named ‘TOTALSTEPS’ which will store the answer
  4. Repeat while the size of max_heap is greater than 0
    • Declare a variable ‘CURMAX’ to store the current maximum value and assign the value of the top element of the max_heap to it.
    • Declare a vector ‘ALLCURMAX’ to store all the elements that are equal to ‘CURMAX’.
    • Repeat while max_heap is not empty and the top element is equal to ‘CURMAX’.
      • Append the top element to the ‘ALLCURMAX’ vector
      • Pop out the top element from the max_heap
    • If the max_heap is not empty then iterate over all the elements in ‘ALLCURMAX’
      • Change each element in ‘ALLCURMAX’ to the next maximum.
      • Increment ‘TOTALSTEPS’ by 1
      • Push the element into the max_heap
  5. Return the value of the variable ‘TOTALSTEPS’.
Time Complexity

O( N * N * log( N ) ), Where N denotes the length of the array ‘HEIGHTS’.

 

We are pushing all the piles into the max_heap which takes a total time of O( N * log( N ) ). Then we are popping all the piles with maximum height and for each pile, we are modifying it and pushing it back into the max_heap. So the total time taken is O( N * N * log( N ) ).

Hence the time complexity is O( N * N * log( N ) ).


 

Space Complexity

O( N ), Where N is the size of the array ‘HEIGHTS’.

 

We are using a priority queue to store the elements. 

Hence space complexity is O( N ).

Code Solution
(100% EXP penalty)
Piles of Boxes
Full screen
Console