Window Median Cost

Easy

0/40

0 upvote

Asked in company

Problem statement

You are given an array of n integers. Your task is to calculate a specific cost for each sliding window of k elements, from left to right.

The cost for a single window is defined as the minimum total cost to make all elements in that window equal. The cost to change an element is the absolute difference between its new value and its original value. The total cost is the sum of these individual costs.

Mathematical Insight: The cost sum(|xi - y|) for a set of numbers xi is minimized when y is the median of the set. Therefore, for each window, you must find its median and then calculate the sum of absolute differences of all elements from that median.

You need to return a list of these costs for each of the n-k+1 windows.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains two integers n and k, the number of elements and the size of the window.

The second line contains n space-separated integers, x_1, x_2, ..., x_n, the contents of the array.

Output Format:

Print a single line containing n-k+1 space-separated integers, representing the calculated costs for each window.

Note:

A brute-force solution that re-sorts each window to find the median will be O(N * K log K) and too slow. The key to an efficient O(N log K) solution is to use a data structure that can maintain the median of a sliding window. The standard approach is to use two balanced heaps (a max-heap for the lower half and a min-heap for the upper half) to track the elements in the current window.

Sample Input 1:

8 3
2 4 3 5 8 1 2 1

Sample Output 1:

2 2 5 7 7 1

Explanation for Sample 1:

Window 1 [2, 4, 3]: Sorted is [2, 3, 4]. The median is 3. Cost = |2-3| + |4-3| + |3-3| = 1 + 1 + 0 = 2.
Window 2 [4, 3, 5]: Sorted is [3, 4, 5]. The median is 4. Cost = |4-4| + |3-4| + |5-4| = 0 + 1 + 1 = 2.
Window 3 [3, 5, 8]: Sorted is [3, 5, 8]. The median is 5. Cost = |3-5| + |5-5| + |8-5| = 2 + 0 + 3 = 5.
Window 4 [5, 8, 1]: Sorted is [1, 5, 8]. The median is 5. Cost = |1-5| + |5-5| + |8-5| = 4 + 0 + 3 = 7.
Window 5 [8, 1, 2]: Sorted is [1, 2, 8]. The median is 2. Cost = |1-2| + |2-2| + |8-2| = 1 + 0 + 6 = 7.
Window 6 [1, 2, 1]: Sorted is [1, 1, 2]. The median is 1. Cost = |1-1| + |1-1| + |2-1| = 0 + 0 + 1 = 2.

Expected Time Complexity:

The expected time complexity is O(N).

Constraints:

1 <= k <= n <= 2 * 10^5
1 <= x_i <= 10^9

Time limit: 1 sec

Approaches (1)

Approach 1

Time Complexity

Space Complexity

(100% EXP penalty)

Window Median Cost

Console