Sliding Window Median

How it works

A single sorted data structure can track all k elements directly. By maintaining a pointer or index to the median position, we can update it efficiently as elements are added and removed. When a new element is inserted before the median or an element before the median is removed, we adjust the median pointer accordingly.

Steps

1. Initialize a sorted container (multiset or sorted list) with the first k elements.
2. Set a median pointer to the element at index k / 2.
3. Compute the first median from the pointer position.
4. For each subsequent element:
   • Insert the new element and adjust the median pointer if the insertion happens before or at the current median.
   • Adjust the median pointer if the element being removed is at or before the current median.
   • Remove the outgoing element from the container.
   • Compute and store the median.
5. Return the array of medians.

Complexity

• Time complexity: O(n log k)
• Space complexity:
  • O(k) extra space.
  • O(n - k + 1) space for output array.

Where n is the size of the array nums and k is the size of the sliding window.

Things to watch for

Integer Overflow When Calculating Median

When k is even, the median is the average of two middle elements. Adding two large integers before dividing can cause overflow. For example, if both elements are near Integer.MAX_VALUE, their sum overflows. Always cast to a larger type (like long) before adding: (a + 0L + b) / 2.0.

Incorrect Heap Balancing After Removal

With the two-heap approach using lazy deletion, the balance between heaps can become incorrect. When an element is marked for deletion but sits in the middle of a heap, the heap sizes appear correct but the actual valid element count differs. Always track balance changes based on which heap the removed element logically belongs to, not just heap sizes.

Removing from Wrong Heap in Two-Heap Approach

When the sliding window moves, the outgoing element must be removed from the correct heap. A common mistake is comparing the outgoing element to the wrong heap's top or using stale comparisons after rebalancing. Always compare with small.top() before any rebalancing operations to determine which heap contains the element.

Not Handling Duplicate Values Correctly

Multisets and sorted lists handle duplicates, but standard sets and maps do not. Using a regular set causes duplicates to be lost, producing incorrect medians. When using a TreeSet in Java, you must store indices (not values) with a custom comparator to distinguish between equal values at different positions.

Off-by-One Errors in Median Index Calculation

For odd k, the median is at index k / 2. For even k, the two middle elements are at indices (k - 1) / 2 and k / 2. Mixing these up or using 1-based indexing instead of 0-based produces wrong results. Verify your indexing by testing with small examples like k = 2 and k = 3.

from typing import List

class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        window = SortedList()
        res = []
        for i in range(len(nums)):
            window.add(nums[i])
            if i >= k:
                window.remove(nums[i - k])
            if i >= k - 1:
                if k % 2 == 1:
                    res.append(float(window[k // 2]))
                else:
                    res.append((window[k // 2 - 1] + window[k // 2]) / 2)
        return res

class Solution {
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        multiset<int> window(nums.begin(), nums.begin() + k);
        auto mid = next(window.begin(), k / 2);
        vector<double> res;

        for (int i = k;; i++) {
            if (k & 1) {
                res.push_back(*mid);
            } else {
                res.push_back((*mid + 0LL + *prev(mid)) / 2.0);
            }

            if (i == nums.size()) return res;

            window.insert(nums[i]);
            if (nums[i] < *mid) mid--;
            if (nums[i - k] <= *mid) mid++;
            window.erase(window.lower_bound(nums[i - k]));
        }
    }
};