Sliding Window Median solution and explanation
Google
9 more videos on this problem
LeetCode - Sliding Window Median (480)Kshittiz K · 17:03 · 20K views
SLIDING WINDOW MEDIAN| LEETCODE 480 | PYTHON TWO-HEAP SOLUTIONCracking FAANG · 30:07 · 20K views
[Java] Leetcode 480. Sliding Window Median [Two Heaps #2]Eric Programming · 15:43 · 13K views
LeetCode 480. Sliding Window MedianHappy Coding · 38:30 · 7K views
Sliding Window Median | Heap Data Structure | LeetCodeCODE STALKER · 5:43 · 6K views
480. Sliding Window Median - English VersionSimple Code - 단순코드 · 15:19 · 4K views
Day 48/90 |⚡Master Sliding Window Median (LeetCode 480) | Lazy Deletion with Two Heaps #6 #heapCTO Bhaiya · 58:06 · 1K views
LeetCode 480 Sliding Window Median - 2 Heaps - JavaCoding Concepts Visualized · 28:11 · 847 views
leetcode 中文 | Sliding Window Median | Two Heaps 基礎概念 2 - Python - 臉書考題 | LeetCode 480.今天比昨天厲害 · 34:15 · 550 views
LEETCODE HARD EXPLAINED: Sliding Window MedianLychee Z · 7:56 · 361 views
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. So the median is the mean of the two middle values.
- For examples, if
arr = [2,3,4], the median is3. - For examples, if
arr = [1,2,3,4], the median is(2 + 3) / 2 = 2.5.
You are given an integer array nums and an integer k. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
Return the median array for each window in the original array. Answers within 10-5 of the actual value will be accepted.
Example 1:
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 --------------- ----- [1 3 -1] -3 5 3 6 7 1 1 [3 -1 -3] 5 3 6 7 -1 1 3 [-1 -3 5] 3 6 7 -1 1 3 -1 [-3 5 3] 6 7 3 1 3 -1 -3 [5 3 6] 7 5 1 3 -1 -3 5 [3 6 7] 6
Example 2:
Input: nums = [1,2,3,4,2,3,1,4,2], k = 3 Output: [2.00000,3.00000,3.00000,3.00000,2.00000,3.00000,2.00000]
Constraints:
1 <= k <= nums.length <= 105-231 <= nums[i] <= 231 - 1
Approach overview
Problem Overview: You are given an integer array and a window size k. As the window slides one step to the right, compute the median of the current window. The challenge is maintaining the median efficiently while elements enter and leave the window.
Approach 1: Brute Force (O(n * k log k) time, O(k) space)
The most direct approach recomputes the median for every window. Extract the k elements in the current window, sort them, and read the middle element (or the average of two middle elements for even k). Sorting costs O(k log k) per window and there are about n - k + 1 windows, resulting in O(n * k log k) time. Space complexity is O(k) to hold the temporary window. This approach is easy to implement and useful for verifying correctness, but it becomes slow when k grows large.
Approach 2: Dual Heap Approach (O(n log k) time, O(k) space)
This is the standard optimal solution. Maintain two heaps: a max heap for the smaller half of numbers and a min heap for the larger half. The heaps stay balanced so their sizes differ by at most one, allowing the median to be read directly from the heap tops. When the window slides, insert the new element and lazily remove the outgoing element using a hash map to track delayed deletions. Each insertion or removal costs O(log k), so processing all elements takes O(n log k) time. This technique combines heap (priority queue) operations with a small hash table for efficient cleanup.
Approach 3: Heap-Based Sliding Window with Lazy Deletion (O(n log k) time, O(k) space)
A variation of the dual heap approach explicitly focuses on lazy deletion. Instead of removing elements immediately when they fall out of the window, mark them in a map and clean them only when they appear at the top of a heap. This avoids expensive arbitrary deletions from a heap. The heaps maintain balance as elements are inserted and invalid ones are popped. Median lookup remains O(1). This method is widely used in competitive programming for sliding window median problems.
Approach 4: Multiset and Iterator (O(n log k) time, O(k) space)
Languages with ordered containers (like multiset in C++ or TreeSet-like structures) allow a different strategy. Store the current window in a balanced binary search tree and maintain an iterator pointing to the median element. When the window moves, insert the incoming value and erase the outgoing one while adjusting the iterator accordingly. Both operations take O(log k). Accessing the median becomes constant time. This approach is clean and deterministic but relies on ordered-set support.
Recommended for interviews: The dual heap approach is what most interviewers expect. It demonstrates understanding of heap balancing, lazy deletion, and sliding window optimization. Showing the brute force first proves you understand the problem, but implementing the O(n log k) heap solution demonstrates strong data structure skills.
Approach 1: Dual Heap Approach
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:
- Use a max heap to store the smaller half of the numbers (lower part).
- Use a min heap to store the larger half of the numbers (upper part).
- When the window slides, update these heaps accordingly.
- The median can be extracted as the maximum from the max heap or by averaging the top of both heaps, depending on the window size (odd/even).
from sortedcontainers import SortedList
class Solution:
def medianSlidingWindow(self, nums, k):
window = SortedList()
medians = []
for i, num in enumerate(nums):
window.add(num)
if len(window) > k:
window.remove(nums[i-k])
if len(window) == k:
if k % 2 == 0:
medians.append((window[k//2-1] + window[k//2]) / 2)
else:
medians.append(window[k//2])
return mediansThis Python solution uses the `SortedList` from the `sortedcontainers` module to maintain an ordered list of numbers in the current window. As the window slides:
- We add the new number and remove the one that's slid out.
- The list remains sorted, allowing easy median computation.
- The `SortedList` maintains order efficiently, ensuring operations stay logarithmic in nature.
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.
Approach 2: Brute Force Approach
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:
- For each window, extract the subarray.
- Sort this subarray to find the median.
- Move the window one element to the right and repeat.
class Solution:
def medianSlidingWindow(self, nums, k):
medians = []
for i in range(len(nums) - k + 1):
window = sorted(nums[i:i + k])
if k % 2 == 0:
medians.append((window[k//2 - 1] + window[k//2]) / 2.0)
else:
medians.append(window[k//2])
return mediansThis straightforward Python solution sorts each subarray individually to determine the median. The simplicity comes at the cost of performance for larger datasets:
- Sort the subarray extracted from nums starting at the current index.
- Compute the median based on the parity of k.
- Collect computed medians for all possible windows.
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.
Approach 3: Heap-Based Approach
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:
- When the sizes of both heaps are equal, the median is the mean of the top elements of both heaps.
- When the size of the max-heap is greater than the min-heap, the median is the top of the max-heap.
Efficient insertion and removal using heaps make this approach suitable for large inputs.
from heapq import heappush, heappop
def medianSlidingWindow(nums, k):
min_heap, max_heap = [], []
medians = []
def add_number(num):
if len(max_heap) == 0 or num <= -max_heap[0]:
heappush(max_heap, -num)
else:
heappush(min_heap, num)
balance_heaps()
def remove_number(num):
if num <= -max_heap[0]:
max_heap.remove(-num)
heapify(max_heap)
else:
min_heap.remove(num)
heapify(min_heap)
balance_heaps()
def balance_heaps():
if len(max_heap) > len(min_heap) + 1:
heappush(min_heap, -heappop(max_heap))
elif len(min_heap) > len(max_heap):
heappush(max_heap, -heappop(min_heap))
for i in range(len(nums)):
add_number(nums[i])
if i >= k - 1:
if len(max_heap) > len(min_heap):
medians.append(float(-max_heap[0]))
else:
medians.append((-max_heap[0] + min_heap[0]) / 2)
remove_number(nums[i - k + 1])
return medians#include <vector>
#include <queue>
#include <iostream>
std::vector<double> medianSlidingWindow(std::vector<int>& nums, int k) {
std::priority_queue<int> max_heap;
std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;
std::vector<double> medians;
auto add_number = [&](int number) {
if (max_heap.empty() || number <= max_heap.top())
max_heap.push(number);
else
min_heap.push(number);
balance_heaps();
};
auto remove_number = [&](int number) {
if (number <= max_heap.top()) {
max_heap.push(INT_MIN); // Add a small number to force closure
max_heap.pop();
} else {
min_heap.push(INT_MAX); // Add a large number to force closure
min_heap.pop();
}
balance_heaps();
};
auto balance_heaps = [&]() {
if (max_heap.size() > min_heap.size() + 1) {
min_heap.push(max_heap.top());
max_heap.pop();
} else if (min_heap.size() > max_heap.size()) {
max_heap.push(min_heap.top());
min_heap.pop();
}
};
for (int i = 0; i < nums.size(); i++) {
add_number(nums[i]);
if (i >= k - 1) {
if (max_heap.size() > min_heap.size())
medians.push_back(max_heap.top());
else
medians.push_back((max_heap.top() + min_heap.top()) / 2.0);
remove_number(nums[i - k + 1]);
}
}
return medians;
}
int main() {
std::vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
std::vector<double> results = medianSlidingWindow(nums, k);
for (double result : results) {
std::cout << result << " " << std::endl;
}
return 0;
}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.
Time Complexity: O(n * log k), due to heap operations per window.
Space Complexity: O(k), for storing elements in the heaps.
Approach 4: Multiset and Iterator Approach
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:
- Elements are inserted and removed from the multiset while the iterator always points to the median or close to it.
- The iterator is adjusted based on the balance between the lower and upper halves.
import java.util.*;
public class SlidingWindowMedian {
public double[] medianSlidingWindow(int[] nums, int k) {
TreeMap<Integer, Integer> window = new TreeMap<>();
double[] medians = new double[nums.length - k + 1];
int left = 0, right = 0;
while (right < k) {
window.put(nums[right], window.getOrDefault(nums[right], 0) + 1);
right++;
}
right--; // Set to last element in initial window
for (; right < nums.length; right++) {
if (right >= k) {
medians[left] = getMedian(window, k);
remove(window, nums[left]);
left++;
}
if (right + 1 < nums.length) {
add(window, nums[right + 1]);
}
}
medians[left] = getMedian(window, k);
return medians;
}
private void add(TreeMap<Integer, Integer> map, int num) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
private void remove(TreeMap<Integer, Integer> map, int num) {
int count = map.get(num);
if (count == 1) {
map.remove(num);
} else {
map.put(num, count - 1);
}
}
private double getMedian(TreeMap<Integer, Integer> map, int k) {
int count = 0;
int midpoint = (k + 1) / 2;
Integer lower = null, upper = null;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
count += entry.getValue();
if (count >= midpoint && lower == null) {
lower = entry.getKey();
}
if (count >= (midpoint + k % 2) / 2) {
upper = entry.getKey();
break;
}
}
return (lower + upper) / 2.0;
}
public static void main(String[] args) {
int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
SlidingWindowMedian swm = new SlidingWindowMedian();
double[] medians = swm.medianSlidingWindow(nums, k);
System.out.println(Arrays.toString(medians));
}
}using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
public double[] MedianSlidingWindow(int[] nums, int k) {
SortedDictionary<int, int> window = new SortedDictionary<int, int>();
double[] medians = new double[nums.Length - k + 1];
int left = 0, right = 0;
void AddNumber(int num) {
if (window.ContainsKey(num))
window[num]++;
else
window[num] = 1;
}
void RemoveNumber(int num) {
if (window[num] == 1)
window.Remove(num);
else
window[num]--;
}
double GetMedian() {
int count = 0;
int midpoint = (k + 1) / 2;
int? lower = null, upper = null;
foreach (var entry in window) {
count += entry.Value;
if (!lower.HasValue && count >= midpoint) {
lower = entry.Key;
}
if (count >= (midpoint + k % 2) / 2) {
upper = entry.Key;
break;
}
}
return (lower.Value + upper.Value) / 2.0;
}
while (right < k) {
AddNumber(nums[right++]);
}
right--; // Adjust to last element in window
for (; right < nums.Length; right++) {
if (right >= k) {
medians[left] = GetMedian();
RemoveNumber(nums[left]);
left++;
}
if (right + 1 < nums.Length) {
AddNumber(nums[right + 1]);
}
}
medians[left] = GetMedian();
return medians;
}
public static void Main() {
int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
var sol = new Solution();
var medians = sol.MedianSlidingWindow(nums, k);
Console.WriteLine(string.Join(", ", medians));
}
}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.
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.
Approach 5: Dual Priority Queues (Min-Heap and Max-Heap) + Lazy Deletion
We can use two priority queues (min-heap and max-heap) to maintain the elements in the current window. One priority queue stores the smaller half of the elements, and the other priority queue stores the larger half of the elements. This way, the median of the current window is either the average of the top elements of the two heaps or one of the top elements.
We design a class MedianFinder to maintain the elements in the current window. This class includes the following methods:
add_num(num): Addsnumto the current window.find_median(): Returns the median of the elements in the current window.remove_num(num): Removesnumfrom the current window.prune(pq): If the top element of the heap is in the lazy deletion dictionarydelayed, it pops the top element from the heap and decrements its lazy deletion count. If the lazy deletion count of the element becomes zero, it removes the element from the lazy deletion dictionary.rebalance(): If the number of elements in the smaller half exceeds the number of elements in the larger half by2, it moves the top element of the larger half to the smaller half. If the number of elements in the smaller half is less than the number of elements in the larger half, it moves the top element of the larger half to the smaller half.
In the add_num(num) method, we first consider adding num to the smaller half. If num is greater than the top element of the larger half, we add num to the larger half. Then we call the rebalance() method to ensure that the size difference between the two priority queues does not exceed 1.
In the remove_num(num) method, we increment the lazy deletion count of num. Then we compare num with the top element of the smaller half. If num is less than or equal to the top element of the smaller half, we update the size of the smaller half and call the prune() method to ensure that the top element of the smaller half is not in the lazy deletion dictionary. Otherwise, we update the size of the larger half and call the prune() method to ensure that the top element of the larger half is not in the lazy deletion dictionary.
In the find_median() method, if the current window size is odd, we return the top element of the smaller half; otherwise, we return the average of the top elements of the smaller half and the larger half.
In the prune(pq) method, if the top element of the heap is in the lazy deletion dictionary, it pops the top element from the heap and decrements its lazy deletion count. If the lazy deletion count of the element becomes zero, it removes the element from the lazy deletion dictionary.
In the rebalance() method, if the number of elements in the smaller half exceeds the number of elements in the larger half by 2, it moves the top element of the larger half to the smaller half. If the number of elements in the smaller half is less than the number of elements in the larger half, it moves the top element of the larger half to the smaller half.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array nums.
type MedianFinder struct {
small hp
large hp
delayed map[int]int
smallSize, largeSize int
k int
}
func Constructor(k int) MedianFinder {
return MedianFinder{hp{}, hp{}, map[int]int{}, 0, 0, k}
}
func (this *MedianFinder) AddNum(num int) {
if this.small.Len() == 0 || num <= -this.small.IntSlice[0] {
heap.Push(&this.small, -num)
this.smallSize++
} else {
heap.Push(&this.large, num)
this.largeSize++
}
this.rebalance()
}
func (this *MedianFinder) FindMedian() float64 {
if this.k&1 == 1 {
return float64(-this.small.IntSlice[0])
}
return float64(-this.small.IntSlice[0]+this.large.IntSlice[0]) / 2
}
func (this *MedianFinder) removeNum(num int) {
this.delayed[num]++
if num <= -this.small.IntSlice[0] {
this.smallSize--
if num == -this.small.IntSlice[0] {
this.prune(&this.small)
}
} else {
this.largeSize--
if num == this.large.IntSlice[0] {
this.prune(&this.large)
}
}
this.rebalance()
}
func (this *MedianFinder) prune(pq *hp) {
sign := 1
if pq == &this.small {
sign = -1
}
for pq.Len() > 0 && this.delayed[sign*pq.IntSlice[0]] > 0 {
this.delayed[sign*pq.IntSlice[0]]--
if this.delayed[sign*pq.IntSlice[0]] == 0 {
delete(this.delayed, sign*pq.IntSlice[0])
}
heap.Pop(pq)
}
}
func (this *MedianFinder) rebalance() {
if this.smallSize > this.largeSize+1 {
heap.Push(&this.large, -heap.Pop(&this.small).(int))
this.smallSize--
this.largeSize++
this.prune(&this.small)
} else if this.smallSize < this.largeSize {
heap.Push(&this.small, -heap.Pop(&this.large).(int))
this.smallSize++
this.largeSize--
this.prune(&this.large)
}
}
func medianSlidingWindow(nums []int, k int) []float64 {
finder := Constructor(k)
for _, num := range nums[:k] {
finder.AddNum(num)
}
ans := []float64{finder.FindMedian()}
for i := k; i < len(nums); i++ {
finder.AddNum(nums[i])
finder.removeNum(nums[i-k])
ans = append(ans, finder.FindMedian())
}
return ans
}
type hp struct{ sort.IntSlice }
func (h hp) Less(i, j int) bool { return h.IntSlice[i] < h.IntSlice[j] }
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
a := h.IntSlice
v := a[len(a)-1]
h.IntSlice = a[:len(a)-1]
return v
}Approach 6: Ordered Set
We can use two ordered sets to maintain the elements in the current window. The ordered set l stores the smaller half of the elements in the current window, and the ordered set r stores the larger half of the elements.
We traverse the array nums. For each element x, we add it to the ordered set r, then move the smallest element in the ordered set r to the ordered set l. If the size of the ordered set l is greater than the size of the ordered set r by more than 1, we move the largest element in the ordered set l to the ordered set r.
If the total number of elements in the current window is k and the size is odd, the maximum value in the ordered set l is the median. If the size of the current window is even, the average of the maximum value in the ordered set l and the minimum value in the ordered set r is the median. Then, we remove the leftmost element of the window and continue traversing the array.
The time complexity is O(n log k), and the space complexity is O(k). Here, n is the length of the array nums.
function medianSlidingWindow(nums: number[], k: number): number[] {
const l = new TreapMultiSet<number>((a, b) => a - b);
const r = new TreapMultiSet<number>((a, b) => a - b);
const n = nums.length;
const ans: number[] = [];
for (let i = 0; i < n; ++i) {
r.add(nums[i]);
l.add(r.shift()!);
while (l.size - r.size > 1) {
r.add(l.pop()!);
}
const j = i - k + 1;
if (j >= 0) {
ans[j] = k % 2 ? l.last()! : (l.last()! + r.first()!) / 2;
if (nums[j] <= l.last()!) {
l.delete(nums[j]);
} else {
r.delete(nums[j]);
}
}
}
return ans;
}
type CompareFunction<T, R extends 'number' | 'boolean'> = (
a: T,
b: T,
) => R extends 'number' ? number : boolean;
interface ITreapMultiSet<T> extends Iterable<T> {
add: (...value: T[]) => this;
has: (value: T) => boolean;
delete: (value: T) => void;
bisectLeft: (value: T) => number;
bisectRight: (value: T) => number;
indexOf: (value: T) => number;
lastIndexOf: (value: T) => number;
at: (index: number) => T | undefined;
first: () => T | undefined;
last: () => T | undefined;
lower: (value: T) => T | undefined;
higher: (value: T) => T | undefined;
floor: (value: T) => T | undefined;
ceil: (value: T) => T | undefined;
shift: () => T | undefined;
pop: (index?: number) => T | undefined;
count: (value: T) => number;
keys: () => IterableIterator<T>;
values: () => IterableIterator<T>;
rvalues: () => IterableIterator<T>;
entries: () => IterableIterator<[number, T]>;
readonly size: number;
}
class TreapNode<T = number> {
value: T;
count: number;
size: number;
priority: number;
left: TreapNode<T> | null;
right: TreapNode<T> | null;
constructor(value: T) {
this.value = value;
this.count = 1;
this.size = 1;
this.priority = Math.random();
this.left = null;
this.right = null;
}
static getSize(node: TreapNode<any> | null): number {
return node?.size ?? 0;
}
static getFac(node: TreapNode<any> | null): number {
return node?.priority ?? 0;
}
pushUp(): void {
let tmp = this.count;
tmp += TreapNode.getSize(this.left);
tmp += TreapNode.getSize(this.right);
this.size = tmp;
}
rotateRight(): TreapNode<T> {
// eslint-disable-next-line @typescript-eslint/no-this-alias
let node: TreapNode<T> = this;
const left = node.left;
node.left = left?.right ?? null;
left && (left.right = node);
left && (node = left);
node.right?.pushUp();
node.pushUp();
return node;
}
rotateLeft(): TreapNode<T> {
// eslint-disable-next-line @typescript-eslint/no-this-alias
let node: TreapNode<T> = this;
const right = node.right;
node.right = right?.left ?? null;
right && (right.left = node);
right && (node = right);
node.left?.pushUp();
node.pushUp();
return node;
}
}
class TreapMultiSet<T = number> implements ITreapMultiSet<T> {
private readonly root: TreapNode<T>;
private readonly compareFn: CompareFunction<T, 'number'>;
private readonly leftBound: T;
private readonly rightBound: T;
constructor(compareFn?: CompareFunction<T, 'number'>);
constructor(compareFn: CompareFunction<T, 'number'>, leftBound: T, rightBound: T);
constructor(
compareFn: CompareFunction<T, any> = (a: any, b: any) => a - b,
leftBound: any = -Infinity,
rightBound: any = Infinity,
) {
this.root = new TreapNode<T>(rightBound);
this.root.priority = Infinity;
this.root.left = new TreapNode<T>(leftBound);
this.root.left.priority = -Infinity;
this.root.pushUp();
this.leftBound = leftBound;
this.rightBound = rightBound;
this.compareFn = compareFn;
}
get size(): number {
return this.root.size - 2;
}
get height(): number {
const getHeight = (node: TreapNode<T> | null): number => {
if (node == null) return 0;
return 1 + Math.max(getHeight(node.left), getHeight(node.right));
};
return getHeight(this.root);
}
/**
*
* @complexity `O(logn)`
* @description Returns true if value is a member.
*/
has(value: T): boolean {
const compare = this.compareFn;
const dfs = (node: TreapNode<T> | null, value: T): boolean => {
if (node == null) return false;
if (compare(node.value, value) === 0) return true;
if (compare(node.value, value) < 0) return dfs(node.right, value);
return dfs(node.left, value);
};
return dfs(this.root, value);
}
/**
*
* @complexity `O(logn)`
* @description Add value to sorted set.
*/
add(...values: T[]): this {
const compare = this.compareFn;
const dfs = (
node: TreapNode<T> | null,
value: T,
parent: TreapNode<T>,
direction: 'left' | 'right',
): void => {
if (node == null) return;
if (compare(node.value, value) === 0) {
node.count++;
node.pushUp();
} else if (compare(node.value, value) > 0) {
if (node.left) {
dfs(node.left, value, node, 'left');
} else {
node.left = new TreapNode(value);
node.pushUp();
}
if (TreapNode.getFac(node.left) > node.priority) {
parent[direction] = node.rotateRight();
}
} else if (compare(node.value, value) < 0) {
if (node.right) {
dfs(node.right, value, node, 'right');
} else {
node.right = new TreapNode(value);
node.pushUp();
}
if (TreapNode.getFac(node.right) > node.priority) {
parent[direction] = node.rotateLeft();
}
}
parent.pushUp();
};
values.forEach(value => dfs(this.root.left, value, this.root, 'left'));
return this;
}
/**
*
* @complexity `O(logn)`
* @description Remove value from sorted set if it is a member.
* If value is not a member, do nothing.
*/
delete(value: T): void {
const compare = this.compareFn;
const dfs = (
node: TreapNode<T> | null,
value: T,
parent: TreapNode<T>,
direction: 'left' | 'right',
): void => {
if (node == null) return;
if (compare(node.value, value) === 0) {
if (node.count > 1) {
node.count--;
node?.pushUp();
} else if (node.left == null && node.right == null) {
parent[direction] = null;
} else {
// 旋到根节点
if (
node.right == null ||
TreapNode.getFac(node.left) > TreapNode.getFac(node.right)
) {
parent[direction] = node.rotateRight();
dfs(parent[direction]?.right ?? null, value, parent[direction]!, 'right');
} else {
parent[direction] = node.rotateLeft();
dfs(parent[direction]?.left ?? null, value, parent[direction]!, 'left');
}
}
} else if (compare(node.value, value) > 0) {
dfs(node.left, value, node, 'left');
} else if (compare(node.value, value) < 0) {
dfs(node.right, value, node, 'right');
}
parent?.pushUp();
};
dfs(this.root.left, value, this.root, 'left');
}
/**
*
* @complexity `O(logn)`
* @description Returns an index to insert value in the sorted set.
* If the value is already present, the insertion point will be before (to the left of) any existing values.
*/
bisectLeft(value: T): number {
const compare = this.compareFn;
const dfs = (node: TreapNode<T> | null, value: T): number => {
if (node == null) return 0;
if (compare(node.value, value) === 0) {
return TreapNode.getSize(node.left);
} else if (compare(node.value, value) > 0) {
return dfs(node.left, value);
} else if (compare(node.value, value) < 0) {
return dfs(node.right, value) + TreapNode.getSize(node.left) + node.count;
}
return 0;
};
return dfs(this.root, value) - 1;
}
/**
*
* @complexity `O(logn)`
* @description Returns an index to insert value in the sorted set.
* If the value is already present, the insertion point will be before (to the right of) any existing values.
*/
bisectRight(value: T): number {
const compare = this.compareFn;
const dfs = (node: TreapNode<T> | null, value: T): number => {
if (node == null) return 0;
if (compare(node.value, value) === 0) {
return TreapNode.getSize(node.left) + node.count;
} else if (compare(node.value, value) > 0) {
return dfs(node.left, value);
} else if (compare(node.value, value) < 0) {
return dfs(node.right, value) + TreapNode.getSize(node.left) + node.count;
}
return 0;
};
return dfs(this.root, value) - 1;
}
/**
*
* @complexity `O(logn)`
* @description Returns the index of the first occurrence of a value in the set, or -1 if it is not present.
*/
indexOf(value: T): number {
const compare = this.compareFn;
let isExist = false;
const dfs = (node: TreapNode<T> | null, value: T): number => {
if (node == null) return 0;
if (compare(node.value, value) === 0) {
isExist = true;
return TreapNode.getSize(node.left);
} else if (compare(node.value, value) > 0) {
return dfs(node.left, value);
} else if (compare(node.value, value) < 0) {
return dfs(node.right, value) + TreapNode.getSize(node.left) + node.count;
}
return 0;
};
const res = dfs(this.root, value) - 1;
return isExist ? res : -1;
}
/**
*
* @complexity `O(logn)`
* @description Returns the index of the last occurrence of a value in the set, or -1 if it is not present.
*/
lastIndexOf(value: T): number {
const compare = this.compareFn;
let isExist = false;
const dfs = (node: TreapNode<T> | null, value: T): number => {
if (node == null) return 0;
if (compare(node.value, value) === 0) {
isExist = true;
return TreapNode.getSize(node.left) + node.count - 1;
} else if (compare(node.value, value) > 0) {
return dfs(node.left, value);
} else if (compare(node.value, value) < 0) {
return dfs(node.right, value) + TreapNode.getSize(node.left) + node.count;
}
return 0;
};
const res = dfs(this.root, value) - 1;
return isExist ? res : -1;
}
/**
*
* @complexity `O(logn)`
* @description Returns the item located at the specified index.
* @param index The zero-based index of the desired code unit. A negative index will count back from the last item.
*/
at(index: number): T | undefined {
if (index < 0) index += this.size;
if (index < 0 || index >= this.size) return undefined;
const dfs = (node: TreapNode<T> | null, rank: number): T | undefined => {
if (node == null) return undefined;
if (TreapNode.getSize(node.left) >= rank) {
return dfs(node.left, rank);
} else if (TreapNode.getSize(node.left) + node.count >= rank) {
return node.value;
} else {
return dfs(node.right, rank - TreapNode.getSize(node.left) - node.count);
}
};
const res = dfs(this.root, index + 2);
return ([this.leftBound, this.rightBound] as any[]).includes(res) ? undefined : res;
}
/**
*
* @complexity `O(logn)`
* @description Find and return the element less than `val`, return `undefined` if no such element found.
*/
lower(value: T): T | undefined {
const compare = this.compareFn;
const dfs = (node: TreapNode<T> | null, value: T): T | undefined => {
if (node == null) return undefined;
if (compare(node.value, value) >= 0) return dfs(node.left, value);
const tmp = dfs(node.right, value);
if (tmp == null || compare(node.value, tmp) > 0) {
return node.value;
} else {
return tmp;
}
};
const res = dfs(this.root, value) as any;
return res === this.leftBound ? undefined : res;
}
/**
*
* @complexity `O(logn)`
* @description Find and return the element greater than `val`, return `undefined` if no such element found.
*/
higher(value: T): T | undefined {
const compare = this.compareFn;
const dfs = (node: TreapNode<T> | null, value: T): T | undefined => {
if (node == null) return undefined;
if (compare(node.value, value) <= 0) return dfs(node.right, value);
const tmp = dfs(node.left, value);
if (tmp == null || compare(node.value, tmp) < 0) {
return node.value;
} else {
return tmp;
}
};
const res = dfs(this.root, value) as any;
return res === this.rightBound ? undefined : res;
}
/**
*
* @complexity `O(logn)`
* @description Find and return the element less than or equal to `val`, return `undefined` if no such element found.
*/
floor(value: T): T | undefined {
const compare = this.compareFn;
const dfs = (node: TreapNode<T> | null, value: T): T | undefined => {
if (node == null) return undefined;
if (compare(node.value, value) === 0) return node.value;
if (compare(node.value, value) >= 0) return dfs(node.left, value);
const tmp = dfs(node.right, value);
if (tmp == null || compare(node.value, tmp) > 0) {
return node.value;
} else {
return tmp;
}
};
const res = dfs(this.root, value) as any;
return res === this.leftBound ? undefined : res;
}
/**
*
* @complexity `O(logn)`
* @description Find and return the element greater than or equal to `val`, return `undefined` if no such element found.
*/
ceil(value: T): T | undefined {
const compare = this.compareFn;
const dfs = (node: TreapNode<T> | null, value: T): T | undefined => {
if (node == null) return undefined;
if (compare(node.value, value) === 0) return node.value;
if (compare(node.value, value) <= 0) return dfs(node.right, value);
const tmp = dfs(node.left, value);
if (tmp == null || compare(node.value, tmp) < 0) {
return node.value;
} else {
return tmp;
}
};
const res = dfs(this.root, value) as any;
return res === this.rightBound ? undefined : res;
}
/**
* @complexity `O(logn)`
* @description
* Returns the last element from set.
* If the set is empty, undefined is returned.
*/
first(): T | undefined {
const iter = this.inOrder();
iter.next();
const res = iter.next().value;
return res === this.rightBound ? undefined : res;
}
/**
* @complexity `O(logn)`
* @description
* Returns the last element from set.
* If the set is empty, undefined is returned .
*/
last(): T | undefined {
const iter = this.reverseInOrder();
iter.next();
const res = iter.next().value;
return res === this.leftBound ? undefined : res;
}
/**
* @complexity `O(logn)`
* @description
* Removes the first element from an set and returns it.
* If the set is empty, undefined is returned and the set is not modified.
*/
shift(): T | undefined {
const first = this.first();
if (first === undefined) return undefined;
this.delete(first);
return first;
}
/**
* @complexity `O(logn)`
* @description
* Removes the last element from an set and returns it.
* If the set is empty, undefined is returned and the set is not modified.
*/
pop(index?: number): T | undefined {
if (index == null) {
const last = this.last();
if (last === undefined) return undefined;
this.delete(last);
return last;
}
const toDelete = this.at(index);
if (toDelete == null) return;
this.delete(toDelete);
return toDelete;
}
/**
*
* @complexity `O(logn)`
* @description
* Returns number of occurrences of value in the sorted set.
*/
count(value: T): number {
const compare = this.compareFn;
const dfs = (node: TreapNode<T> | null, value: T): number => {
if (node == null) return 0;
if (compare(node.value, value) === 0) return node.count;
if (compare(node.value, value) < 0) return dfs(node.right, value);
return dfs(node.left, value);
};
return dfs(this.root, value);
}
*[Symbol.iterator](): Generator<T, any, any> {
yield* this.values();
}
/**
* @description
* Returns an iterable of keys in the set.
*/
*keys(): Generator<T, any, any> {
yield* this.values();
}
/**
* @description
* Returns an iterable of values in the set.
*/
*values(): Generator<T, any, any> {
const iter = this.inOrder();
iter.next();
const steps = this.size;
for (let _ = 0; _ < steps; _++) {
yield iter.next().value;
}
}
/**
* @description
* Returns a generator for reversed order traversing the set.
*/
*rvalues(): Generator<T, any, any> {
const iter = this.reverseInOrder();
iter.next();
const steps = this.size;
for (let _ = 0; _ < steps; _++) {
yield iter.next().value;
}
}
/**
* @description
* Returns an iterable of key, value pairs for every entry in the set.
*/
*entries(): IterableIterator<[number, T]> {
const iter = this.inOrder();
iter.next();
const steps = this.size;
for (let i = 0; i < steps; i++) {
yield [i, iter.next().value];
}
}
private *inOrder(root: TreapNode<T> | null = this.root): Generator<T, any, any> {
if (root == null) return;
yield* this.inOrder(root.left);
const count = root.count;
for (let _ = 0; _ < count; _++) {
yield root.value;
}
yield* this.inOrder(root.right);
}
private *reverseInOrder(root: TreapNode<T> | null = this.root): Generator<T, any, any> {
if (root == null) return;
yield* this.reverseInOrder(root.right);
const count = root.count;
for (let _ = 0; _ < count; _++) {
yield root.value;
}
yield* this.reverseInOrder(root.left);
}
}func medianSlidingWindow(nums []int, k int) (ans []float64) {
l := redblacktree.New[int, int]()
r := redblacktree.New[int, int]()
merge := func(st *redblacktree.Tree[int, int], x, v int) {
c, _ := st.Get(x)
if c+v == 0 {
st.Remove(x)
} else {
st.Put(x, c+v)
}
}
lSize, rSize := 0, 0
for i, x := range nums {
merge(r, x, 1)
x = r.Left().Key
merge(r, x, -1)
merge(l, x, 1)
lSize++
for lSize-rSize > 1 {
x = l.Right().Key
merge(l, x, -1)
merge(r, x, 1)
lSize--
rSize++
}
if j := i - k + 1; j >= 0 {
if k%2 == 1 {
ans = append(ans, float64(l.Right().Key))
} else {
ans = append(ans, float64(l.Right().Key+r.Left().Key)/2)
}
if x = nums[j]; x <= l.Right().Key {
merge(l, x, -1)
lSize--
} else {
merge(r, x, -1)
rSize--
}
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dual Heap Approach | 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. |
| Brute Force Approach | 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. |
| Heap-Based Approach | Time Complexity: O(n * log k), due to heap operations per window. Space Complexity: O(k), for storing elements in the heaps. |
| Multiset and Iterator Approach | 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. |
| Dual Priority Queues (Min-Heap and Max-Heap) + Lazy Deletion | – |
| Ordered Set | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Sorting | O(n * k log k) | O(k) | Small window sizes or quick correctness check |
| Dual Heap (Max Heap + Min Heap) | O(n log k) | O(k) | General optimal solution for interviews and production |
| Heap with Lazy Deletion | O(n log k) | O(k) | When implementing sliding window medians efficiently with priority queues |
| Multiset / Balanced BST | O(n log k) | O(k) | Languages with ordered sets like C++ or Java Tree structures |
Frequently asked questions
Is Sliding Window Median easy or hard?
Sliding Window Median is classified as a hard problem because it requires combining sliding window logic with advanced data structures like heaps or balanced trees. Managing deletions and maintaining median balance makes the implementation tricky.
Sliding Window Median Python or Java solution
Python solutions usually rely on two heaps using the heapq module with lazy deletion through a dictionary. Java implementations often use PriorityQueue or TreeMap structures to maintain ordered elements and compute medians efficiently.
How to solve Sliding Window Median in O(n log k)?
Use two heaps to keep track of the smaller and larger halves of the current window. Insert the incoming element into the correct heap, mark outgoing elements for lazy deletion, and rebalance the heaps so their sizes differ by at most one. The median is always available from the heap tops.
What is the best approach for Sliding Window Median?
The dual heap approach is the most common optimal solution. It maintains two heaps: a max heap for the lower half and a min heap for the upper half of the window. With lazy deletion for elements leaving the window, each update costs O(log k), giving an overall complexity of O(n log k).
What data structure is used in Sliding Window Median?
The most common data structures are two heaps (a max heap and a min heap) combined with a hash map for lazy deletion. Alternative implementations use balanced binary search trees such as multiset or TreeMap-based structures.
What is the time complexity of Sliding Window Median?
The optimal solutions run in O(n log k) time where n is the array size and k is the window size. Each insertion or removal from the heaps or balanced tree takes O(log k). The brute force approach that sorts each window costs O(n * k log k).
Is Sliding Window Median asked at Google Amazon or Meta?
Sliding Window Median is considered a classic hard interview problem and has appeared in interviews at companies like Google, Amazon, and Meta. It tests heap usage, balancing logic, and efficient sliding window updates.