Last Updated: 9 Jun, 2022
Piles of Boxes
Moderate
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.
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
Approaches
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):
- Declare a max_heap.
- Push each pile into the max_heap.
- Declare a variable named ‘TOTALSTEPS’ which will store the answer
- 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
- Return the value of the variable ‘TOTALSTEPS’.
First, we need to sort the array. Then we traverse the array in reverse. For each pile in sorted order, we will try to find the number of steps required to make the height of this pile equal to the height of the pile with minimum height. To do so, we need to know how many intermediate heights it will be changed to. We can find the number of the intermediate by finding the number of distinct heights between the minimum height and the height of the pile.
For example, if heights = [2, 3, 4, 5], the pile with height ‘5’ will have (3, 4) as intermediate heights. The number of distinct heights between 2 and 5 is also (3, 4).
We can calculate the intermediate heights by using a hashtable. The sum of the intermediate heights of all piles will give us the required steps.
The steps are as follows:-
Function getTotalSteps(vector<int>& heights):
- Sort the array in increasing order.
- Declare a variable named ‘TOTALSTEPS’ which will store the answer.
- Declare a map to store all the elements.
- Iterate over all the piles in the array
- Store each pile on the map
- Traverse the array in reverse.
- Calculate the number of distinct heights for each i (use map.size() function).
- Increment the ‘TOTALSTEPS’ by the number of distinct elements - 1.
- Decrement the value of element ‘HEIGHTS[i]’ in the map by 1.
- If the value of element ‘HEIGHTS[i]’ in the map drops to 0 erase that element from the map
- Return the value of the variable’TOTALSTEPS’.