Sliding Window Median Problem


Description

LeetCode Problem 480.

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:

1
2
3
4
5
6
7
8
9
10
11
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:

1
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


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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> medians;
        
        for (int i=k; ; i++) {
            // Push the current median.
            medians.push_back((double(*mid) + *prev(mid, 1 - k%2)) / 2);

            // If all done, return.
            if (i == nums.size())
                return medians;

            // Insert nums[i].
            window.insert(nums[i]);
            if (nums[i] < *mid)
                mid--;

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




Related Posts

Shortest Subarray With Sum At Least K Problem

LeetCode 862. Given an integer array nums and an integer...

Reachable Nodes In Subdivided Graph Problem

LeetCode 882. You are given an undirected graph (the “original...

Minimum Number Of Refueling Stops Problem

LeetCode 871. A car travels from a starting position to...

Minimum Cost To Hire K Workers Problem

LeetCode 857. There are n workers. You are given two...

K Closest Points To Origin Problem

LeetCode 973. Given an array of points where points[i] =...

Swim In Rising Water Problem

LeetCode 778. You are given an n x n integer...