Leetcode 480. Sliding Window Median

Problem Explanation:

The problem basically needs us to calculate the median for each and every sliding window of size k in a given array nums, that starts from the very beginning of the array and moves to the very end, one position at a time.

Here's an example to better explain the problem:

• Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

1
2
3Starting from the first three elements: [1 3 -1]; 
4The median is calculated by arranging the elements in ascending order [1 -1 3], and picking the middle element
5Thus the median is 1.
6
7When the window slides to the next three elements: [3 -1 -3];
8After arranging them in ascending order [-3 -1 3], the median is -1.
9
10The window continues to move to the right, repeating this process until it reaches the end of the array.

The reported medians for the example above are: [1,-1,-1,3,5,6]

Approach:

The solution involves using a multiset data structure, STL (Standard Template Library) in C++. Multisets are a type of associative containers similar to set, with an exception that multiple elements can have equivalent values.

The executable code below uses a multiset to keep track of the current window of numbers in the array and where the median is. A multiset is a sorted container, so it allows for efficient access to the median elements. The median is the arithmetic mean of the middle two elements if the window's size is even or the middle element if the window's size is odd.

Java

1
2java
3class Solution {
4    public double[] medianSlidingWindow(int[] nums, int k) {
5        double[] result = new double[nums.length - k + 1];
6        TreeSet<Integer> window = new TreeSet<>((a, b) -> a == b ? 1 : Integer.compare(nums[a], nums[b]));
7        for (int i = 0; i < k; i++) window.add(i);
8        for (int i = 0; i < nums.length - k + 1; i++) {
9            Double median;
10            int midId = (k & 1) != 0 ? window.first() : (Integer)window.toArray()[k/2-1];
11            median = ((long)nums[midId]  + nums[(Integer)window.toArray()[k/2]]) / 2.0;
12            result[i] = median;
13            window.remove(i);
14            if (i + k < nums.length) window.add(i + k);
15        }
16        return result;
17    }
18}

Python

1
2python
3from sortedcontainers import SortedList
4
5class Solution:
6    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
7        s = SortedList(nums[:k])
8        res = []
9        for i in range(k, len(nums) + 1):
10            res.append((s[(k - 1) // 2] + s[k // 2]) / 2)
11            if i == len(nums): 
12                break
13            s.remove(nums[i - k])
14            s.add(nums[i])
15            
16        return res

Javascript

1
2js
3var medianSlidingWindow = function(nums, k) {
4    let windows = nums.slice(0, k).sort((a, b) => a - b);
5    let medians = [];
6    let isEven = k % 2 === 0;
7
8    for (let i = k; i <= nums.length; i++) {
9        medians.push(isEven ? (windows[k/2-1] + windows[k/2]) / 2 : windows[Math.floor(k/2)]);
10        if (i === nums.length) break;
11
12        let index = bisect(windows, nums[i - k]);
13        windows.splice(index, 1);
14        index = bisect(windows, nums[i]);
15        windows.splice(index, 0, nums[i]);
16    }
17
18    function bisect(arr, target) {
19        let low = 0, high = arr.length;
20        while (low < high) {
21            let mid = Math.floor((low + high) / 2);
22            if (arr[mid] < target) low = mid + 1;
23            else high = mid;
24        }
25
26        return low;
27    }
28
29    return medians;
30};

C#

1
2cs
3public class Solution {
4    public double[] MedianSlidingWindow(int[] nums, int k) {
5        double[] median = new double[nums.Length - k + 1];
6        SortedSet<int> window = new SortedSet<int>();
7        Dictionary<int, int> hashtable = new Dictionary<int, int>();
8        for(int i = 0; i < k; i++) {
9            window.Add(i);
10        }
11        int median_ptr = 0;
12        for(int i = k; i <= nums.Length; i++) {
13            median[median_ptr++] = FindMedian(nums, window, k);
14            if(i == nums.Length) break;
15            window.Remove(i - k);
16            if(window.Contains(i))
17                hashtable[i] = 1;
18            window.Add(i);
19            if(hashtable.ContainsKey(i - k)) {
20                hashtable.Remove(i - k);
21                window.Remove(i - k);
22            }
23        }
24        return median;
25    }
26    private double FindMedian(int[] nums, SortedSet<int> window, int k) {
27        double median = 0;
28        int idx = 0, i = 0;
29        foreach(int win in window) {
30            if(idx == k / 2)
31                median += nums[win];
32            if((k % 2 == 0) && (idx == k / 2 - 1))
33                median += nums[win];
34            idx++;
35        }
36        return median / (k % 2 == 0 ? 2 : 1);
37    }
38}

C++

1
2c++
3class Solution {
4public:
5    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
6        multiset<int> window(nums.begin(), nums.begin() + k);
7        auto mid = next(window.begin(), k / 2);
8        vector<double> medians;
9        for (int i=k; ; i++) {
10
11            medians.push_back((double(*mid) + *prev(mid, 1 - k%2)) / 2);
12
13            if (i == nums.size())
14                return medians;
15
16            window.insert(nums[i]);
17            if (nums[i] < *mid)
18                mid--;
19
20            if (nums[i-k] <= *mid)
21                mid++;
22            window.erase(window.lower_bound(nums[i-k]));
23        }
24    }
25};

These solutions have a time complexity of O(n log k) for sorting and adding/removing elements to/from the multiset, and space complexity of O(n) for the result medians array and the multiset.The respective solutions to this problem in various programming languages basically apply the same algorithm flow. The notion is to keep a sorted set (i.e., multiset, SortedList, TreeSet, etc.) of the current window of numbers in the array and keep track of where the median is.

In Java, the TreeSet is used because of its properties of automatically sorting and updating the elements in it. The SortedList container in Python has the same properties. But unlike TreeSet in Java, SortedList permits equal elements. Similarly, the sorted function in JavaScript also provides the benefit of automatic sorting. A custom binary search function is used to find the insertion index in JavaScript. In C#, a combination of SortedSet and a dictionary (for duplicate values) are used to maintain the sliding window of elements in sorted order.

In Python, Java, Javascript, C# and C++, we start by adding the first k elements into the sorted container. Then, we simply iterate through the array, always ensuring the sorted window is of size k, either by adding a new element or by removing the oldest one. As the window is always sorted, we take the average of the middle elements as the median and add this to the result.

All of these solutions get a time complexity of O(n log k) since every insertion and deletion from a sorted set or equivalent Python and JS functions is O(log k), and we're doing this for N elements. Like-wise, all of them have a space complexity of O(n) as they insert N elements into the result array.

As a programmer, understanding how to use data structures and language-specific functions efficiently can help tackle these types of problems with relative ease. While these solutions have practical applications like calculating real-time median for streaming data (sensor data, stock prices, etc.), the concepts they demonstrate are also frequently used in technical interviews. So, mastering these techniques can be highly beneficial.

It's worth noting that there are other solutions to the problem that might employ other ways to keep the window sorted for faster median calculation. Some languages or libraries might even have specific functions to directly solve it. However, the above solutions are quite standard and work in a variety of languages.