Sponsored
Sponsored
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):
3Use 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
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
This straightforward Python solution sorts each subarray individually to determine the median. The simplicity comes at the cost of performance for larger datasets:
This 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.
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.