LeetCode: Sliding Window Median

Posted on March 2, 2018July 26, 2020 by braindenny

Sliding Window Median

Similar Problems:

Find Median from Data Stream
Tag: #heap, #slidingwindow, #getmedian

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.

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.

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: k is always smaller than input array’s size for non-empty array.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

## https://code.dennyzhang.com/sliding-window-median
class Solution:
    ## Basic Ideas: two heap
    ## Complexity: Time O(n*k), Space O(k)
    def medianSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[float]
        """
        import heapq
        l1, l2 = [], []
        maxHeap = heapq.heapify(l1)
        minHeap = heapq.heapify(l2)

        res = []
        for i in range(len(nums)):
            heapq.heappush(l1, -nums[i])

            if i<k-1: continue

            # rebalancing
            while len(l1) > len(l2):
                heapq.heappush(l2, -heapq.heappop(l1))

            # collect results
            item = (-l1[0] + l2[0])/2 if k%2==0 else float(l2[0])
            res.append(item)            

            # remove item
            if self.heapRemove(l1, -nums[i-k+1]):
                # Notice: If we delete from l1, move one back from l2 to l1
                heapq.heappush(l1, -heapq.heappop(l2))
            else:
                self.heapRemove(l2, nums[i-k+1])
        return res

    def heapRemove(self, l, item):
        k = -1
        for i in range(len(l)):
            if l[i] == item:
                k = i
                break
        if k != -1:
            l[k] = l[0]
            heapq.heappop(l)
            heapq.heapify(l)
            return True
        return False

    ## Basic Ideas: insert with binary search
    ## Complexity: Time O(n*k), Space O(k)
    def medianSlidingWindow_v1(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[float]
        """
        import bisect
        res = []
        window = sorted(nums[:k])
        for a, b in zip(nums, nums[k:]+[0]):
            res.append((window[int(k/2)] + window[~int(k/2)])/2)
            window.remove(a)
            bisect.insort(window, b)
        return res

Post Views: 5