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.
1import java.util.*;
2
3public class SlidingWindowMedian {
4
5 public double[] medianSlidingWindow(int[] nums, int k) {
6 TreeMap<Integer, Integer> window = new TreeMap<>();
7 double[] medians = new double[nums.length - k + 1];
8 int left = 0, right = 0;
9
10 while (right < k) {
11 window.put(nums[right], window.getOrDefault(nums[right], 0) + 1);
12 right++;
13 }
14 right--; // Set to last element in initial window
15
16 for (; right < nums.length; right++) {
17 if (right >= k) {
18 medians[left] = getMedian(window, k);
19 remove(window, nums[left]);
20 left++;
21 }
22
23 if (right + 1 < nums.length) {
24 add(window, nums[right + 1]);
25 }
26 }
27
28 medians[left] = getMedian(window, k);
29
30 return medians;
31 }
32
33 private void add(TreeMap<Integer, Integer> map, int num) {
34 map.put(num, map.getOrDefault(num, 0) + 1);
35 }
36
37 private void remove(TreeMap<Integer, Integer> map, int num) {
38 int count = map.get(num);
39 if (count == 1) {
40 map.remove(num);
41 } else {
42 map.put(num, count - 1);
43 }
44 }
45
46 private double getMedian(TreeMap<Integer, Integer> map, int k) {
47 int count = 0;
48 int midpoint = (k + 1) / 2;
49 Integer lower = null, upper = null;
50
51 for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
52 count += entry.getValue();
53 if (count >= midpoint && lower == null) {
54 lower = entry.getKey();
55 }
56 if (count >= (midpoint + k % 2) / 2) {
57 upper = entry.getKey();
58 break;
59 }
60 }
61
62 return (lower + upper) / 2.0;
63 }
64
65 public static void main(String[] args) {
66 int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
67 int k = 3;
68 SlidingWindowMedian swm = new SlidingWindowMedian();
69 double[] medians = swm.medianSlidingWindow(nums, k);
70 System.out.println(Arrays.toString(medians));
71 }
72}This Java implementation utilizes a TreeMap to store the elements of the current window. Functions to add and remove elements adjust the frequency count within the set, allowing us to maintain window data. getMedian then determines the median based on the current state of the window.