Game of Dominoes

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

Problem statement

Rafiq loves to play with dominoes. On his birthday his father gifted him ‘N’ piles of dominoes, where each pile contains a positive number of dominoes stacked above.

Rafiq loves to play with piles if they are of equal heights, so his father decides to make changes to the piles. His father wonders for each consecutive window of length ‘K’ what is the minimum cost to make them all of the equal height. Hence his father wants to calculate the cost for each window.

The cost for removing and adding one domino on any pile is one unit.

Determine what is the cost to make all elements equal in a window of size 'K', for all windows of size 'K' in an 'N'-sized array/list 'heights'.

Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain a single integer ‘N’ i.e., length of the pile and ‘K’ size of the window.

The next line of each test case contains 'N' numbers a1, a2, a3... aN denoting the initial height of each pile.
Output Format: 
For each test case, output the minimum cost for each window.

Output for every test case will be printed in a separate line.
Note: 
You don’t need to print anything; It has already been taken care of.
Constraints: 
1 <= T <= 10
1 <= N <= 10000 
1 <= K <= N 
1 <= height[i] <= 10^5 

where 'T' is the number of test cases, 'N' is the number of piles, 'K' is the size of the window as discussed above and 'height[i]' represents the height of each pile.

Time limit: 1 sec
Sample Input 1:
1
6 2
2 4 1 1 2 3
Sample Output 1:
2 3 0 1 1
Explanation of sample input 1:
All the windows or subarray of size 2 are [2,4] , [4,1] , [1,1] , [1,2] , [2,3]. The cost of each subarray is 2,3,0,1,1.
Sample Input 2:
1
6 3
3 1 1 1 4 4
Sample Output 2:
2 0 3 3
Explanation of sample input 2:
All the windows or subarray of size 3 are [3,1,1] , [1,1,1] , [1,1,4] , [1,4,4] , [2,3]. The cost of each subarray is 2,0,3,3.
Hint

Try to notice that the optimal cost to make all elements equal is at the median of that window.

Approaches (3)
Brute Force

Let's reduce our question to a fixed array instead of every subarray of size ‘K’ and try to find an answer specific to that array/list ‘height’, so we could do the same thing for each window, now, as mentioned in the hint, we need to calculate the sum of absolute difference of every element from its median, so after getting the new array, next step would be to calculate the cost of that window, so first we will sort the array and select the ‘K’/2 th element as we know the size of the new array will be ‘K’, now we could calculate the cost easily by iterating over the window.

 

Reference: proof for optimal cost to make all elements equal would be at its median value.

 

The steps are as follows:

 

  1. Declare a list/vector ‘ret’ in which we store our answer.
  2. Run a loop while ‘i’ = 0 to ‘N’ - ‘K’.
    • Let's calculate the median of the ‘K’ size subarray/sublist ‘temp’ and initialize it as ‘Median’. Note that there are various methods to calculate the median of the ‘temp’.
      • select the ‘N’/2 th element in the sorted ‘temp’, here ‘N’ denotes the size of the ‘temp’.
      • Use kth-order statistics to find the median in linear time.
    • For each element ‘X’ in the ‘temp’, we add abs(‘X’ - ‘Median’) to ‘Answer’, as we need this quantity of steps to make ‘X’ equal to ‘Median’, by incrementing or decrementing ‘X’ by 1.
    • Add this ‘Answer’ into ‘ret’.
  3. Finally, return 'ret'.

 

Time Complexity

O(K*log(K) * (‘N’ - ‘K’ + 1)). where ‘N’ is the length of the ‘pile’ and ‘K’ is the size of the window.

 

As we know there is a total ‘N’ - ‘K’ + 1 window in a total of size ‘K’ and as we are doing this for each window or subarray our overall time complexity will be O(‘K * log(K)’ * (‘N’ - ‘K’ + 1)). 

Space Complexity

O(N) where ‘N’ is the length of the array/list ‘pile’ .

 

As we are only traversing the array and storing only constant variables, also please note that we are ignoring the space complexity for sort functions we are using. As space complexity of sort depends on the method of the sort we are using. Hence, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Game of Dominoes
Full screen
Console