Sliding Window Median

LeetCode 480 | Difficulty: Hard

Hard

Problem Description

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 is `3`.

- 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 <= 10^5`

- `-2^31 <= nums[i] <= 2^31 - 1`

Topics: Array, Hash Table, Sliding Window, Heap (Priority Queue)

---

Approach

Sliding Window

Maintain a window [left, right] over the array/string. Expand right to include new elements, and shrink left when the window violates constraints. Track the optimal answer as the window slides.

When to use

Finding subarrays/substrings with a property (max length, min length, exact count).

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

---

Solutions

Solution 1: C# (Best: 514 ms)

Metric	Value
Runtime	514 ms
Memory	47.2 MB
Date	2022-02-06

Solution

public class Solution {
  public double[] MedianSlidingWindow(int[] nums, int k)
{   
    var left = new PriorityQueue<int>(Comparer<int>.Create((x, y) => y.CompareTo(x)));
    var right = new PriorityQueue<int>();
    int n = nums.Length;
    var res = new double[n - k + 1];

    for (var i = 0; i < nums.Length; i++)
    {
        int val = nums[i];
        if (left.Count() <= right.Count())
        {
            right.Enqueue(nums[i]);
            left.Enqueue(right.Dequeue());
        }
        else
        {
            left.Enqueue(nums[i]);
            right.Enqueue(left.Dequeue());
        }

        if (i >= k - 1)
        {
            double median = GetMedian(left, right);
            int start = i - k + 1;
            res[start] = median;
            if (left.Contains(nums[start]))
                left.Remove(nums[start]);
            else
                right.Remove(nums[start]);
        }
    }
    return res;
}
    private double GetMedian(PriorityQueue<int> left, PriorityQueue<int> right)
{
    if (left.size == right.size) return left.size == 0 ? 0 : ((double)left.Peek() + (double)right.Peek()) / 2.0;
    else return (left.size > right.size) ? left.Peek() : right.Peek();
}
}

public class PriorityQueue<T> where T : IComparable<T>
{
    public SortedDictionary<T, int> data;
    public int size = 0;
    private readonly int? capacity;

    public PriorityQueue(int? capacity = null)
    {
        this.data = new SortedDictionary<T, int>();
        this.capacity = capacity;
    }

    public PriorityQueue(IComparer<T> comparer, int? capacity = null)
    {
        this.data = new SortedDictionary<T, int>(comparer);
        this.capacity = capacity;
    }

    public void Enqueue(T item)
    {
        if (capacity.HasValue && capacity == size) Dequeue();
        if (data.ContainsKey(item))
        {
            data[item]++;
        }
        else
        {
            data.Add(item, 1);
        }
        size++;
    }

    public T Dequeue()
    {
        var front = data.First();
        if (front.Value == 1) data.Remove(front.Key);
        else data[front.Key]--;
        size--;
        return front.Key;
    }

    public bool Contains(T item)
    {
        return data.ContainsKey(item);
    }

    public void Remove(T item)
    {
        if (data[item] == 1) data.Remove(item);
        else data[item]--;
        size--;
    }

    public T Peek()
    {
        return data.First().Key;
    }

    public int Count()
    {
        return size;
    }
}

---

Complexity Analysis

Approach	Time	Space
Sliding Window	$O(n)$	$O(k)$
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Break the problem into smaller subproblems. Communicate your approach before coding.
• Clarify what makes a window "valid" and what triggers expansion vs shrinking.
• Hash map gives O(1) lookup — think about what to use as key vs value.
• LeetCode provides 3 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: The simplest of solutions comes from the basic idea of finding the median given a set of numbers. We know that by definition, a median is the center element (or an average of the two center elements). Given an unsorted list of numbers, how do we find the median element? If you know the answer to this question, can we extend this idea to every sliding window that we come across in the array?

Hint 2: Is there a better way to do what we are doing in the above hint? Don't you think there is duplication of calculation being done there? Is there some sort of optimization that we can do to achieve the same result? This approach is merely a modification of the basic approach except that it simply reduces duplication of calculations once done.

Hint 3: The third line of thought is also based on this same idea but achieving the result in a different way. We obviously need the window to be sorted for us to be able to find the median. Is there a data-structure out there that we can use (in one or more quantities) to obtain the median element extremely fast, say O(1) time while having the ability to perform the other operations fairly efficiently as well?