Sliding Window Median

---

Sliding Window Median: 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

---

Try this Problem on your own or check similar problems:

1. Find Median from Data Stream

Solution:

Java

class Solution {
  public double[] medianSlidingWindow(int[] nums, int k) {
      double[] result = new double[nums.length - k + 1];
      TreeSet<Integer> max = new TreeSet<>((a, b) -> nums[b] == nums[a] ? a - b : Integer.compare(nums[b], nums[a]));
      TreeSet<Integer> min = new TreeSet<>((a, b) -> nums[b] == nums[a] ? a - b : Integer.compare(nums[a], nums[b]));

      for(int i = 0; i < nums.length; ++i){
          if(i - k >= 0){
            if (!max.remove(i - k)) {
                min.remove(i - k);
            }
          }

          max.add(i);
          balanceTrees(nums, max, min);

          if (i - k + 1 >= 0) {
              result[i - k + 1] = getMedian(nums, k, max, min);
          }
      }

      return result;
  }

  private void balanceTrees(int[] nums, TreeSet<Integer> max, TreeSet<Integer> min){
      if(max.size() > min.size() + 1){
          min.add(max.pollFirst());
      }

      if(!min.isEmpty() && nums[min.first()] < nums[max.first()]){
          int temp = min.pollFirst();
          min.add(max.pollFirst());
          max.add(temp);
      }
  }
  private double getMedian(int[] nums, int k, TreeSet<Integer> max, TreeSet<Integer> min){
      if(max.size() > min.size()) return (double) nums[max.first()];
      return ((double)nums[max.first()] + nums[min.first()]) / 2.0;
  }
}

JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var medianSlidingWindow = function (nums, k) {
  let l = 0,
    r = k - 1,
    ret = [];

  const window = nums.slice(l, k);
  window.sort((a, b) => a - b);
  while (r < nums.length) {
    const median =
      k % 2 === 0
        ? (window[Math.floor(k / 2) - 1] + window[Math.floor(k / 2)]) / 2
        : window[Math.floor(k / 2)];
    ret.push(median);

    let char = nums[l++];
    let index = binarySearch(window, char, 0, window.length - 1);
    window.splice(index, 1);

    char = nums[++r];
    index = binarySearch(window, char, 0, window.length - 1);
    window.splice(index, 0, char);
  }
  return ret;
};

function binarySearch(arr, target, l, r) {
  while (l < r) {
    const mid = Math.floor((l + r) / 2);
    if (arr[mid] < target) l = mid + 1;
    else if (arr[mid] > target) r = mid;
    else return mid;
  }
  if (l === r) return arr[l] >= target ? l : l + 1;
}

Python

class Solution:
    def medianSlidingWindow(self, nums: List[int], k: int) -> List[float]:
        max_heap = []
        min_heap = []
        heap_dict = defaultdict(int)
        result = []

        for i in range(k):
            heappush(max_heap, -nums[i])
            heappush(min_heap, -heappop(max_heap))
            if len(min_heap) > len(max_heap):
                heappush(max_heap, -heappop(min_heap))

        median = self.find_median(max_heap, min_heap, k)
        result.append(median)

        for i in range(k, len(nums)):
            prev_num = nums[i - k]
            heap_dict[prev_num] += 1

            balance = -1 if prev_num <= median else 1

            if nums[i] <= median:
                balance += 1
                heappush(max_heap, -nums[i])
            else:
                balance -= 1
                heappush(min_heap, nums[i])

            if balance < 0:
                heappush(max_heap, -heappop(min_heap))
            elif balance > 0:
                heappush(min_heap, -heappop(max_heap))

            while max_heap and heap_dict[-max_heap[0]] > 0:
                heap_dict[-max_heap[0]] -= 1
                heappop(max_heap)

            while min_heap and heap_dict[min_heap[0]] > 0:
                heap_dict[min_heap[0]] -= 1
                heappop(min_heap)

            median = self.find_median(max_heap, min_heap, k)
            result.append(median)

        return result

    def find_median(self, max_heap, min_heap, heap_size):
        if heap_size % 2 == 1:
            return -max_heap[0]
        else:
            return (-max_heap[0] + min_heap[0]) / 2

C++

class Solution {
public:
    vector<double> medianSlidingWindow(vector<int>& nums, int k) {
        vector<double> result;

        for(int i=0; i<nums.size(); i++)
        {
            if(i >= k)
            {
                if(minH.find(nums[i-k]) != minH.end()) minH.erase(minH.find(nums[i-k]));
                else maxH.erase(maxH.find(nums[i-k]));
            }

            minH.insert(nums[i]);
            maxH.insert(*minH.begin());
            minH.erase(minH.begin());

            balanceHeaps();

            if(i >= k-1) result.push_back(getMedian(k));
        }

        return result;
    }

private:
    multiset<double> minH;
    multiset<double, greater<double>> maxH;

    void balanceHeaps()
    {
        if(maxH.size() > minH.size())
        {
            minH.insert(*maxH.begin());
            maxH.erase(maxH.begin());
        }
    }

    double getMedian(int k)
    {
        if(k%2 == 0)
            return (*minH.begin() + *maxH.begin())*0.5;
        else return *minH.begin();
    }
};

---

Time/Space Complexity:

• Time Complexity: O(nlogk)
• Space Complexity: O(k)

---

Explanation:

The solution is actually combination of implementations of Find Median from Data Stream (where we have utilized balancing method and extract it to a method balanceTrees and getMedian to retrieve the median using two heaps) and Sliding Window Maximum (where we have utilized the discard index method to remove indices that are out of window when shifting the window to the right, and also the approach to fill in nums.length - k + 1 array). There are few traps to take note on:

• First we should use Integer.compare(nums[b], nums[a]) instead of nums[b]-nums[a] since allows us to cope with Integer.MIN_VALUE and Intger.MAX_VALUE which are allowed in input array by the problem constraints
• When balancing the heaps, we should compare its value in nums not their raw value since we're dealing with indices not the real array value inside heaps
• We're using TreeSet since they enable us to remove/random access in O(logk)
• One thing to note is that TreeSet are sensitive to duplicates (since they're sets, they will only store one occurrence of each repeating element), to cope with this we use indices instead of real array value.

The time complexity is time required to traverse the input array each time doing TreeSet operations O(logk) leading to O(nlogk) with space complexity equal to the number of elements we hold in TreeSet which can be at most the size of window k.