Summary of Ideas and an accepting solution


  • 2
    G

    Solution

    Sliding Window Median https://leetcode.com/problems/sliding-window-median/

    Ideas

    • List to store the window : Maintain a sliding window and keep sorting it. O(NKLg(K))
    • List to store the window: Maintain a sorted window. Add and remove elements from it to maintain sorted variant. O(NK).
    • BST to store the window: Create a special BST where a node has size and frequency field. size refers to the number of nodes in its subtree. frequency is the number of occurences of the key. Then median is a rank() operation which is average case Log(K). Average case complexity: NKlog(K). Worst case complexity: O(NK).
    • 2 Heaps to store the median: Online median algorithm can be used to tackle the incoming part of the stream. Removal can be lazy. Just store what needs to be removed in a hash-table. Check the top element of the heap to see if it is marked for removal before using it for median computation. O(N * lgN)

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

    List to store the window: O((n-k) * klg(k)). TLE

    • Brute force simple slides across all windows and reports the minimum.
    class Solution(object):
        def medianSlidingWindow(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: List[float]
            """
            result = []
            for i in range(0, len(nums)-k+1):
                x = sorted(nums[i:i+k])
                if len(x) % 2 == 0:
                    median = (x[(len(x)//2) - 1] + x[(len(x)//2)])/2.0
                else:
                    median = x[len(x)//2]
                result.append(float(median))
            return result
    

    List to : Sorted List with O(nk). Accepted.

    • Maintain a sorted window. Use remove and bisect.insort() modules.
    from bisect import insort        
    class Solution(object):
        def get_median(self, x):
            N = len(x)
            median = (x[N//2 - 1] + x[N//2])/2. if N % 2 == 0 else x[N//2]/1.
            return median
        
        def medianSlidingWindow(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: List[float]
            """
            window = sorted(nums[:k])
            result = []
            result.append(self.get_median(window))
            for i in range(k,len(nums)):
                window.remove(nums[i-k])
                insort(window, nums[i])
                result.append(self.get_median(window))
            return result
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.