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'.

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).

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)). 

'''



    Time Complexity : O(K * log(K) * (N - k +1))

    Space Complexity : O(N)



    where N is the number of pile and K is the size of the window.



'''



def getMin(heights, n, k):



    #W Declaring list for storing cost for each window.

    ret = []

    

    for i in range(0, n - k + 1): 



        # Declaring window [ i , i + k ).

        temp = heights[i : i + k]



        # Sorting to get median easily, also  nth_element in c++ stl could be used instead.

        # Median  = temp[k / 2]

        temp.sort()        

        

        cost = 0

        median = temp[k // 2]



        # Calculating cost by adding all the cost to convert each element to median.

        for x in temp:

            cost += abs(x - median)



        ret.append(cost)



    return ret

/*



    Time Complexity : O(K * log(K) * (N - k +1))

    Space Complexity : O(N)



    where N is the number of pile and K is the size of the window.



*/



vector getMin(vector &heights, int n, int k)

{

    auto &x = heights;



    // Declaring list for storing cost for each window.

    vector ret;

    

    for (int i = 0; i + k <= n; i++)

    {

        // Declaring window [ i , i + k ].

        vector temp(begin(x) + i, begin(x) + i + k);



        // Sorting to get median easily, also  nth_element in c++ stl could be used instead.

        // Median  = temp[k / 2]

        sort(begin(temp), end(temp));

        

        int cost = 0;

        int median = temp[k / 2];



        // Calculating cost by adding all the cost to convert each element to median.

        for (int x : temp)

        {

            cost += abs(x - median);

        }



        ret.emplace_back(cost);

    }

    

    return ret;

}

/*



	Time Complexity : O((K*log(K)) * (N - K + 1))

	Space Complexity : O(N)



	where N is the number of pile and K is the size of the window.





*/



import java.util.ArrayList;

import java.util.Arrays;



public class Solution 

{

	public static ArrayList getMin(int heights[], int n, int k) 

    {

		// Declaring list for storing cost for each window.

		ArrayList ret = new ArrayList<>();

		

        for (int i = 0; i + k <= n; i++)

        {

			// Declaring window [ i , i + k ].

			int temp[] = new int[k];

            

			for (int j = 0; j < k; j++) 

            {

				temp[j] = heights[i + j];

			}



			// Sorting to get median easily, also nth_element in c++ stl could be used

			Arrays.sort(temp);



			int cost = 0;

			

            // Calculating cost by adding all the cost to convert each element to median.

			for (int j = 0; j < k; j++) 

            {

				cost += Math.abs(temp[j] - temp[k / 2]);

			}



			ret.add(cost);

		}



		return ret;

	}

}

Now as we know that we have to convert each element in the window to the median of that window to get the optimal cost. A median of the window is equal to the element at th...read more

If you could notice what we did in Approach-2, all we need is the sum of half elements and the sum of the other half elements. Also, we need the median of this window, we...read more