Sliding Window Median — LeetCode 480 Python Solution
HardArrayHash TableSliding WindowHeap (Priority Queue)
- Problem
- #480
- Pattern
- Sliding Window
- Reading time
- 11 min
- Source
- leetcode.com
The problem
The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value.
Example
- Input
- nums = [1,3,-1,-3,5,3,6,7], k = 3
- Output
- [1.00000,-1.00000,-1.00000,3.00000,5.00000,6.00000]
- Explanation
- Window position Median
Python solution
Python
class MedianFinder:
def __init__(self, k: int):
self.k = k
self.small = []
self.large = []
self.delayed = defaultdict(int)
self.small_size = 0
self.large_size = 0
def add_num(self, num: int):
if not self.small or num <= -self.small[0]:
heappush(self.small, -num)
self.small_size += 1
else:
heappush(self.large, num)
self.large_size += 1
self.rebalance()
def find_median(self) -> float:
return -self.small[0] if self.k & 1 else (-self.small[0] + self.large[0]) / 2
def remove_num(self, num: int):
self.delayed[num] += 1
if num <= -self.small[0]:
self.small_size -= 1
if num == -self.small[0]:
self.prune(self.small)
else:
self.large_size -= 1
if num == self.large[0]:
self.prune(self.large)
self.rebalance()
def prune(self, pq: List[int]):
sign = -1 if pq is self.small else 1
while pq and sign * pq[0] in self.delayed:
self.delayed[sign * pq[0]] -= 1
if self.delayed[sign * pq[0]] == 0:
self.delayed.pop(sign * pq[0])
heappop(pq)
def rebalance(self):
if self.small_size > self.large_size + 1:
heappush(self.large, -heappop(self.small))
self.small_size -= 1
self.large_size += 1
self.prune(self.small)
elif self.small_size < self.large_size:
heappush(self.small, -heappop(self.large))
self.large_size -= 1
self.small_size += 1
self.prune(self.large)
class Solution:
def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
finder = MedianFinder(k)
for x in nums[:k]:
finder.add_num(x)
ans = [finder.find_median()]
for i in range(k, len(nums)):
finder.add_num(nums[i])
finder.remove_num(nums[i - k])
ans.append(finder.find_median())
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n \times \log n) |
| Space | O(n) auxiliary |
Pattern: Sliding Window
Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 480. Sliding Window Median is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.
The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 480. Sliding Window Median?
- LeetCode 480. Sliding Window Median is rated Hard on LeetCode.
- What is the time complexity of LeetCode 480. Sliding Window Median?
- The Python solution on this page runs in O(n \times \log n).
- What is the space complexity of LeetCode 480. Sliding Window Median?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 480. Sliding Window Median cover?
- LeetCode 480. Sliding Window Median is tagged Array, Hash Table, Sliding Window and Heap (Priority Queue) on LeetCode.