The dual heap approach uses two heaps to maintain the sliding window median. The idea is to maintain a max heap for the left half of the data and a min heap for the right half. This allows for efficient retrieval of the median at any point:
Time Complexity: O(n log k), where n is the number of elements in nums and k is the window size because insertion and deletion in a SortedList take O(log k) time.
Space Complexity: O(k) because we store at most k elements in the SortedList.
1from sortedcontainers import SortedList
2
3class Solution:
4 def medianSlidingWindow(self, nums, k):
5 window = SortedList()
6 medians = []
7 for i, num in enumerate(nums):
8 window.add(num)
9 if len(window) > k:
10 window.remove(nums[i-k])
11 if len(window) == k:
12 if k % 2 == 0:
13 medians.append((window[k//2-1] + window[k//2]) / 2)
14 else:
15 medians.append(window[k//2])
16 return medians
17This Python solution uses the `SortedList` from the `sortedcontainers` module to maintain an ordered list of numbers in the current window. As the window slides:
This approach iteratively computes the median for each possible window by sorting the window at each step. This is a simpler approach but less efficient:
Time Complexity: O(nk log k) due to sorting each subarray of size k for every possible window.
Space Complexity: O(k) to store the current window’s elements temporarily.
1class Solution:
2 def medianSlidingWindow(self, nums, k):
3 medians = []
4 for i in range(len(nums) - k + 1):
5 window = sorted(nums[i:i + k])
6 if k % 2 == 0:
7 medians.append((window[k//2 - 1] + window[k//2]) / 2.0)
8 else:
9 medians.append(window[k//2])
10 return medians
11This straightforward Python solution sorts each subarray individually to determine the median. The simplicity comes at the cost of performance for larger datasets:
Use two heaps: a max-heap to keep track of the lower half of the window and a min-heap for the upper half. The max-heap stores the smaller half of numbers, while the min-heap stores the larger half. By maintaining the size property (balance) of these heaps, we can always pull the median based on the size of the window:
Efficient insertion and removal using heaps make this approach suitable for large inputs.
Time Complexity: O(n * log k), due to heap operations per window.
Space Complexity: O(k), for storing elements in the heaps.
1from heapq import heappush, heappop
2
3def medianSlidingWindow(nums, k):
4 min_heap, max_heap = [], []
5 medians = []
6
7 def add_number(num):
8 if len(max_heap) == 0 or num <= -max_heap[0]:
9 heappush(max_heap, -num)
10 else:
11 heappush(min_heap, num)
12 balance_heaps()
13
14 def remove_number(num):
15 if num <= -max_heap[0]:
16 max_heap.remove(-num)
17 heapify(max_heap)
18 else:
19 min_heap.remove(num)
20 heapify(min_heap)
21 balance_heaps()
22
23 def balance_heaps():
24 if len(max_heap) > len(min_heap) + 1:
25 heappush(min_heap, -heappop(max_heap))
26 elif len(min_heap) > len(max_heap):
27 heappush(max_heap, -heappop(min_heap))
28
29 for i in range(len(nums)):
30 add_number(nums[i])
31 if i >= k - 1:
32 if len(max_heap) > len(min_heap):
33 medians.append(float(-max_heap[0]))
34 else:
35 medians.append((-max_heap[0] + min_heap[0]) / 2)
36 remove_number(nums[i - k + 1])
37
38 return mediansThis solution defines three core functions: add_number to handle numbers entering the heap, remove_number deals with numbers leaving the heap, and balance_heaps keeps the two heaps balanced. The median is calculated based on the sizes of the heaps after adjusting them.
Using a balanced binary search tree structure (like C++ STL's multiset) that maintains order can help efficiently find medians. This approach utilizes iterators, which allow seamless tracking of median positions as we move the sliding window:
Time Complexity: O(n * log k), due to tree operations within each window adjustment.
Space Complexity: O(k), for tracking window elements within the tree.
1using System;
2using System.Collections.Generic;
3using System.Linq;
4
5public class Solution {
6 public double[] MedianSlidingWindow(int[] nums, int k) {
7 SortedDictionary<int, int> window = new SortedDictionary<int, int>();
8 double[] medians = new double[nums.Length - k + 1];
9 int left = 0, right = 0;
10
11 void AddNumber(int num) {
12 if (window.ContainsKey(num))
13 window[num]++;
14 else
15 window[num] = 1;
16 }
17
18 void RemoveNumber(int num) {
19 if (window[num] == 1)
20 window.Remove(num);
21 else
22 window[num]--;
23 }
24
25 double GetMedian() {
26 int count = 0;
27 int midpoint = (k + 1) / 2;
28 int? lower = null, upper = null;
29
30 foreach (var entry in window) {
31 count += entry.Value;
32 if (!lower.HasValue && count >= midpoint) {
33 lower = entry.Key;
34 }
35 if (count >= (midpoint + k % 2) / 2) {
36 upper = entry.Key;
37 break;
38 }
39 }
40 return (lower.Value + upper.Value) / 2.0;
41 }
42
43 while (right < k) {
44 AddNumber(nums[right++]);
45 }
46
47 right--; // Adjust to last element in window
48
49 for (; right < nums.Length; right++) {
50 if (right >= k) {
51 medians[left] = GetMedian();
52 RemoveNumber(nums[left]);
53 left++;
54 }
55
56 if (right + 1 < nums.Length) {
57 AddNumber(nums[right + 1]);
58 }
59 }
60
61 medians[left] = GetMedian();
62
63 return medians;
64 }
65
66 public static void Main() {
67 int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
68 int k = 3;
69 var sol = new Solution();
70 var medians = sol.MedianSlidingWindow(nums, k);
71 Console.WriteLine(string.Join(", ", medians));
72 }
73}The C# implementation uses a sorted dictionary to manage the counts and order of numbers in the window. Add and remove operations modify this dictionary. The GetMedian function determines the median based on the set order and current window size, iterating over sorted keys to reach the median position.