Sliding Window Median

Given an array of integers nums and an integer k, you need to find the median of each window of size k moving from left to right in the array. The window slides by one position each time.

The median of a window is the middle element of the sorted array of elements in that window if the window size is odd. If the window size is even, the median is the average of the two middle elements.

Sample Input/Output:

Let’s consider a sample input:

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

Expected Output:

[1.0, -1.0, -1.0, 3.0, 5.0, 6.0]

Explanation:
The median for the first window [1, 3, -1] is 1.0 (median of [1, 3, -1] is 1.0).

The median for the second window [3, -1, -3] is -1.0 (median of [3, -1, -3] is -1.0).

The median for the third window [-1, -3, 5] is -1.0 (median of [-1, -3, 5] is -1.0).

Time and Space Complexity:

The time complexity of the solution will be O(n * log(k)), where n is the size of the input array nums and k is the window size. We have to maintain a sorted set of elements for each window of size k, and the insertion and deletion operations in the set take O(log(k)) time.

The space complexity will be O(k) to store the elements in the sliding window.

C++ Solution:

#include <iostream>
#include <vector>
#include <set>

using namespace std;

vector<double> medianSlidingWindow(vector<int>& nums, int k) {
    vector<double> result;
    multiset<int> window(nums.begin(), nums.begin() + k);

    auto midIter = next(window.begin(), k / 2);
    for (int i = k; i <= nums.size(); ++i) {
        if (k % 2 == 0) {
            result.push_back((static_cast<double>(*midIter) + *prev(midIter)) / 2.0);
        } else {
            result.push_back(static_cast<double>(*midIter));
        }

        if (i == nums.size()) break;

        window.insert(nums[i]);
        if (nums[i] < *midIter) {
            midIter--;
        }

        if (nums[i - k] <= *midIter) {
            midIter++;
        }
        window.erase(window.lower_bound(nums[i - k]));
    }

    return result;
}

int main() {
    vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;

    vector<double> result = medianSlidingWindow(nums, k);

    cout << "Medians of sliding windows:\n";
    for (double median : result) {
        cout << median << " ";
    }
    cout << endl;

    return 0;
}

In this implementation, we use a multiset to maintain a sorted set of elements in the current sliding window. We keep track of the middle iterator (midIter) to calculate the median efficiently.

The function medianSlidingWindow iterates through the array, and at each step, it calculates the median of the current window and pushes it into the result vector. The function also maintains the sorted set of elements in the current window by inserting the new element and removing the outgoing element when the window slides.

The main function demonstrates the usage of medianSlidingWindow by finding the medians of sliding windows for the given input array and window size.

The output for the provided test case will be:

Medians of sliding windows:
1 -1 -1 3 5 6