How do you solve Sliding Window Median on LeetCode?

Sliding Window Median (LeetCode #480) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log k) time complexity and O(k) space complexity. Key insight: Using heaps allows for efficient median calculation without sorting the entire window.

What is the brute force solution for Sliding Window Median?

The brute force approach for Sliding Window Median is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves calculating the median for each sliding window by extracting the elements, sorting them, and then finding the median. This is straightforward but inefficient due to repeated calculations. The optimal Optimal Solution approach improves this to O(n log k).

What algorithm or data structure is used to solve Sliding Window Median?

Sliding Window Median uses the following concepts: Array, Hash Table, Sliding Window, Heap (Priority Queue). The recommended patterns to study are: Heap, Sliding Window.

What are the interview tips for Sliding Window Median?

Explain your thought process clearly and ask clarifying questions about the problem. Discuss the brute force approach first to demonstrate your understanding before moving to optimizations. Practice implementing heap operations, as they are crucial for this problem type.

What are common mistakes when solving Sliding Window Median?

Failing to properly balance the heaps after adding or removing elements. Not considering edge cases where k is even or odd when calculating the median.

#480

Sliding Window Median

Hard

ArrayHash TableSliding WindowHeap (Priority Queue)HeapSliding Window

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log k)
Space	O(1)	O(k)

💡

Intuition

Time O(n log k)Space O(k)

The optimal solution uses two heaps to maintain the lower and upper halves of the current window. This allows us to efficiently find the median as the window slides, avoiding the need to sort the entire window each time.

⚙️

Algorithm

5 steps

1Step 1: Initialize two heaps: a max-heap for the lower half and a min-heap for the upper half.
2Step 2: For the first k elements, add them to the appropriate heaps to balance them.
3Step 3: For each new element added to the window, add it to the appropriate heap and rebalance if necessary.
4Step 4: Calculate the median based on the sizes of the heaps.
5Step 5: Slide the window by removing the element that is going out of the window and rebalance the heaps.

solution.py33 lines

1import heapq
2
3def medianSlidingWindow(nums, k):
4    def add(num):
5        heapq.heappush(max_heap, -num)
6        heapq.heappush(min_heap, -heapq.heappop(max_heap))
7
8    def remove(num):
9        if num <= -max_heap[0]:
10            max_heap.remove(-num)
11            heapq.heapify(max_heap)
12        else:
13            min_heap.remove(num)
14            heapq.heapify(min_heap)
15
16    def get_median():
17        if k % 2 == 0:
18            return (-max_heap[0] + min_heap[0]) / 2
19        return -max_heap[0]
20
21    max_heap, min_heap = [], []
22    medians = []
23
24    for i in range(k):
25        add(nums[i])
26    medians.append(get_median())
27
28    for i in range(k, len(nums)):
29        add(nums[i])
30        remove(nums[i - k])
31        medians.append(get_median())
32
33    return medians

ℹ

Complexity note: The time complexity is O(n log k) because for each of the n elements, we perform log k operations to add and remove elements from the heaps. The space complexity is O(k) as we store at most k elements in the heaps.

1Using heaps allows for efficient median calculation without sorting the entire window.
2Balancing the heaps ensures that we can always access the median in constant time.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.