480. Sliding Window Median

https://leetcode.com/problems/sliding-window-median/

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 value.

1
2
3
4
Examples: 
[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Given an array nums, 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. Your job is to output the median array for each window in the original array.

1
2
3
4
5
6
7
8
9
10
11
12
For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

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
Therefore, return the median sliding window as [1,-1,-1,3,5,6].

Note:

You may assume k is always valid, ie: 1 ≤ k ≤ input array’s size for non-empty array.


java


https://discuss.leetcode.com/topic/74724/java-solution-using-two-priorityqueues

Java solution using two PriorityQueues

Almost the same idea of Find Median from Data Stream https://leetcode.com/problems/find-median-from-data-stream/

  1. Use two Heaps to store numbers. maxHeap for numbers smaller than current median, minHeap for numbers bigger than and equal to current median. A small trick I used is always make size of minHeap equal (when there are even numbers) or 1 element more (when there are odd numbers) than the size of maxHeap. Then it will become very easy to calculate current median.
  2. Keep adding number from the right side of the sliding window and remove number from left side of the sliding window. And keep adding current median to the result.
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
public class Solution {
PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(
new Comparator<Integer>() {
public int compare(Integer i1, Integer i2) {
return i2.compareTo(i1);
}
}
);

public double[] medianSlidingWindow(int[] nums, int k) {
int n = nums.length - k + 1;
if (n <= 0) return new double[0];
double[] result = new double[n];

for (int i = 0; i <= nums.length; i++) {
if (i >= k) {
result[i - k] = getMedian();
remove(nums[i - k]);
}
if (i < nums.length) {
add(nums[i]);
}
}

return result;
}

private void add(int num) {
if (num < getMedian()) {
maxHeap.add(num);
}
else {
minHeap.add(num);
}
if (maxHeap.size() > minHeap.size()) {
minHeap.add(maxHeap.poll());
}
if (minHeap.size() - maxHeap.size() > 1) {
maxHeap.add(minHeap.poll());
}
}

private void remove(int num) {
if (num < getMedian()) {
maxHeap.remove(num);
}
else {
minHeap.remove(num);
}
if (maxHeap.size() > minHeap.size()) {
minHeap.add(maxHeap.poll());
}
if (minHeap.size() - maxHeap.size() > 1) {
maxHeap.add(minHeap.poll());
}
}

private double getMedian() {
if (maxHeap.isEmpty() && minHeap.isEmpty()) return 0;

if (maxHeap.size() == minHeap.size()) {
return ((double)maxHeap.peek() + (double)minHeap.peek()) / 2.0;
}
else {
return (double)minHeap.peek();
}
}
}

cpp


https://discuss.leetcode.com/topic/74963/o-n-log-k-c-using-multiset-and-updating-middle-iterator

Keep the window elements in a multiset and keep an iterator pointing to the middle value (to “index” k/2, to be precise). Thanks to @votrubac’s solution and comments.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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) + *next(mid, k%2 - 1)) / 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]));
}
}

https://discuss.leetcode.com/topic/74679/o-n-log-n-time-c-solution-using-two-heaps-and-a-hash-table

O(n* log(n)) Time C++ Solution Using Two Heaps and a Hash Table

There are a few solutions using BST with worst case time complexity O(n*k), but we know k can be become large. I wanted to come up with a solution that is guaranteed to run in O(n* log(n)) time. This is in my opinion the best solution so far.

The idea is inspired by solutions to Find Median from Data Stream: use two heaps to store numbers in the sliding window. However there is the issue of numbers moving out of the window, and it turns out that a hash table that records these numbers will just work (and is surprisingly neat). The recorded numbers will only be deleted when they come to the top of the heaps.

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
vector<double> medianSlidingWindow(vector<int>& nums, int k) {
vector<double> medians;
unordered_map<int, int> hash; // count numbers to be deleted
priority_queue<int, vector<int>> bheap; // heap on the bottom
priority_queue<int, vector<int>, greater<int>> theap; // heap on the top

int i = 0;

// Initialize the heaps
while (i < k) { bheap.push(nums[i++]); }
for (int count = k/2; count > 0; --count) {
theap.push(bheap.top()); bheap.pop();
}

while (true) {
// Get median
if (k % 2) medians.push_back(bheap.top());
else medians.push_back( ((double)bheap.top() + theap.top()) / 2 );

if (i == nums.size()) break;
int m = nums[i-k], n = nums[i++], balance = 0;

// What happens to the number m that is moving out of the window
if (m <= bheap.top()) { --balance; if (m == bheap.top()) bheap.pop(); else ++hash[m]; }
else { ++balance; if (m == theap.top()) theap.pop(); else ++hash[m]; }

// Insert the new number n that enters the window
if (!bheap.empty() && n <= bheap.top()) { ++balance; bheap.push(n); }
else { --balance; theap.push(n); }

// Rebalance the bottom and top heaps
if (balance < 0) { bheap.push(theap.top()); theap.pop(); }
else if (balance > 0) { theap.push(bheap.top()); bheap.pop(); }

// Remove numbers that should be discarded at the top of the two heaps
while (!bheap.empty() && hash[bheap.top()]) { --hash[bheap.top()]; bheap.pop(); }
while (!theap.empty() && hash[theap.top()]) { --hash[theap.top()]; theap.pop(); }
}

return medians;
}
};

Since both heaps will never have a size greater than n, the time complexity is O(n* log(n)) in the worst case.


https://discuss.leetcode.com/topic/74577/c-solution-o-n-k

C++ Solution O(n* k)

The idea is to maintain a BST of the window and just search for the k/2 largest element and k/2 smallest element then the average of these two is the median of the window.

Now if the STL’s multiset BST maintained how many element were in each subtree finding each median would take O(log k) time but since it doesn’t it takes O(k) time to find each median.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public:
vector<double> medianSlidingWindow(vector<int>& nums, int k) {
multiset<int> mp;
vector<double> med;

for(int i=0; i<k-1; ++i) mp.insert(nums[i]);

for(int i=k-1; i< nums.size(); ++i){
mp.insert(nums[i]); // Add the next number

auto itb = mp.begin(); advance(itb, (k-1)/2); //Find the lower median
auto ite = mp.end(); advance(ite, -(k+1)/2); //Find the upper median

double avg = ((long)(*itb) + (*ite)) / 2.0;
med.push_back(avg);

mp.erase(mp.find(nums[i-k+1])); //Remove the oldest element
}

return med;
}
};

python


https://discuss.leetcode.com/topic/74634/easy-python-o-nk

Easy Python O(nk)

Just keep the window as a sorted list.

1
2
3
4
5
6
7
8
def medianSlidingWindow(self, nums, k):
window = sorted(nums[:k])
medians = []
for a, b in zip(nums, nums[k:] + [0]):
medians.append((window[k/2] + window[~(k/2)]) / 2.)
window.remove(a)
bisect.insort(window, b)
return medians
谢谢你,可爱的朋友。