Sliding Window Median

Problem Statement

The median of an integer list is the value separating the higher half from the lower half of data when the list is sorted. If the list has an odd number of values, the median is the middle value. If the list has an even number of values, the median is calculated as the mean (average) of the two middle numbers.

Given an integer array nums and an integer k, you have to compute the median for each consecutive subarray of size k as it slides from the left end to the right end of the array. This means for every element e from nums[k-1] to nums[nums.length - 1], we consider the subarray nums[e-k+1] to nums[e], sort it, and then find its median. The task is to return the list of these medians for each sliding window of size k.

Examples

Example 1

Input:

nums = [1,3,-1,-3,5,3,6,7], k = 3

Output:

[1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000]

Explanation:

Window position → Median
------------------------
[1 3 -1] -3 5 3 6 7 → 1.0  
1 [3 -1 -3] 5 3 6 7 → -1.0  
1 3 [-1 -3 5] 3 6 7 → -1.0  
1 3 -1 [-3 5 3] 6 7 → 3.0  
1 3 -1 -3 [5 3 6] 7 → 5.0  
1 3 -1 -3 5 [3 6 7] → 6.0

Example 2

Input:

nums = [1,2,3,4,2,3,1,4,2], k = 3

Output:

[2.00000,3.00000,3.00000,3.00000,2.00000,3.00000,2.00000]

Explanation:

Sliding window medians from left to right:
[1 2 3] → 2.0  
[2 3 4] → 3.0  
[3 4 2] → 3.0  
[4 2 3] → 3.0  
[2 3 1] → 2.0  
[3 1 4] → 3.0  
[1 4 2] → 2.0

Constraints

• 1 <= k <= nums.length <= 10^5
• -2^31 <= nums[i] <= 2^31 - 1

Approach and Intuition

1. Understanding the Sliding Window:

   • A sliding window of size k iteratively captures k consecutive elements in the array. For each step to the right, the window excludes the first element of the current window and includes the next element in the sequence.

2. Finding Median in a Window:

   • If k is odd, the median is the middle element of the sorted window.
   • If k is even, the median is the average of the two middle elements in the sorted window.
   • The position of these middle elements can be directly calculated using integer division and careful indexing.

3. Efficient Window Updates:

   • Directly sorting the window array of size k for each position in nums could be inefficient (especially for large values of k and nums.length), given that the operation might go up to O(k log k) for sorting each window.
   • Efficient data structures such as balanced binary search trees, heaps (two heaps), or self-balancing binary search trees can be used whereby insertion and deletion (required for moving the window) occur in logarithmic time. These structures help maintain a continuously sorted state of the window.

4. Streamlined Computations:

   • Using an appropriate data structure, updating the window (adding the new element from the right and removing the old element from the left) and finding the median can be performed more efficiently.
   • Each step involves adding a new element, removing an old element (except for the first window), finding the median, and then moving to the next step.

By employing the above steps using an effective approach and selecting the right data structures, the problem of finding the median of each sliding window of k elements in nums can be solved efficiently.

Solutions

vector<double> slidingWindowMedian(vector<int>& input, int windowSize)
{
    vector<double> result;
    multiset<int> window(input.begin(), input.begin() + windowSize);

    auto middle = next(window.begin(), windowSize / 2);

    for (int index = windowSize;; index++) {

        // Add current median to result
        result.push_back(((double)(*middle) + *next(middle, windowSize % 2 - 1)) * 0.5);

        // End loop if no more elements to process
        if (index == input.size())
            break;

        // Add the incoming element to the window
        window.insert(input[index]);
        if (input[index] < *middle)
            middle--;               // move the middle pointer backward

        // Remove the outgoing element
        if (input[index - windowSize] <= *middle)
            middle++;               // move the middle pointer forward

        window.erase(window.lower_bound(input[index - windowSize]));
    }

    return result;
}