Easy Python O(nk)


  • 8

    Just keep the window as a sorted list.

    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

  • 0

    Good! It's hard for python to get accepted for this kind of problem due to lack of built-in data structures.


  • 0

    @jedihy Yeah, I've seen/done this a few times now, doing a fast O(k) instead of O(log k). Right now it's still the only posted Python way for this problem... I guess it could be done with heaps, haven't thought about it much.


  • 0

    I have done it with two heaps in Python but I got TLE because there is no efficient way to remove element in a heap unless you implement your own hash heap.


  • 0

    @jedihy You could try removing lazily, I think this solution might work in Python as well: https://discuss.leetcode.com/topic/74679/o-n-log-n-time-c-solution-using-two-heaps-and-a-hash-table


  • 0
    Z

    @StefanPochmann with two heaps we have to implement the random delete in O(log(k/2)) time with hash table, it is something like to store the heap element as the key in the dict and the heap index as the value, whenever we want to delete an element, we could check the dict for the index in expected O(1) time, then copy the end of the heap to this index and follow by a bubble down operation. I haven't thought about how to handle duplicates with this data structure yet, probably using a list of indexes in the dict, e.g. {element: [idx1, idx2]}.


  • 0
    Z

    @StefanPochmann lazy removal is a good idea!


  • 0
    A

    @StefanPochmann I tried to emulate the solution there, but I am not getting the correct answers. I'm not sure what I did wrong, I passed over the code and compared it multiple times.

    class Solution(object):
        def medianSlidingWindow(self, nums, k):
            
            medians = []
            hashes = collections.defaultdict(int)
            bheap, theap = [], []
            
            i = 0
            
            while(i<k):
                heappush(bheap, nums[i])
                i+=1
            for _ in range(k/2, 0, -1):
                heappush(theap, -heappop(bheap))
            
            while True:
                if (k % 2):
                    medians.append(float(bheap[0]))
                else:
                    medians.append((bheap[0]+-theap[0]) / 2.0)
                
                if (i == len(nums)):
                    break
                
                m, n, balance = nums[i-k], nums[i], 0
                i+=1
                
                if m <= bheap[0]:
                    balance-=1
                    if (m == bheap[0]):
                        heappop(bheap)
                    else:
                        hashes[m]+=1
                else: 
                    balance+=1
                    if m == -theap[0]:
                        heappop(theap)
                    else:
                        hashes[m]+=1
                
                if bheap and n <= bheap[0]:  
                    balance+=1
                    heappush(bheap, n)
                else:
                    balance-=1
                    heappush(theap,-n)
                
                if balance < 0:
                    heappush(bheap,-heappop(theap))
                elif balance > 0:
                    heappush(theap, -heappop(bheap))
                
                while bheap and hashes[bheap[0]]:
                    hashes[heappop(bheap)]-=1
                while theap and hashes[theap[0]]:
                    hashes[-heappop(theap)]-=1
            
            return medians
    

  • 2
    Z

    Hi abilityfun, you almost got it right except two things, one big mistake and one small mistake.

    small mistake:
    you are saving theap[0] in hashes, should be -theap[0], I think it just a typo.

    big mistake:
    In c++ by default, the priority_queue is a Max heap, "greater" type defines a Min heap, you should be careful when you are converting code from one language to another, maybe this is what confused you, in this problem, all values in the min heap should be greater than or equal to ones in the max heap.

    class Solution(object):
        def medianSlidingWindow(self, nums, k):
            
            medians = []
            hashes = collections.defaultdict(int)
            bheap, theap = [], []
            
            i = 0
            
            while(i<k):
                heappush(bheap, nums[i])
                i+=1
            for _ in range(k/2, 0, -1):
                heappush(theap, -heappop(bheap))
            
            while True:
                if (k % 2):
                    medians.append(float(bheap[0]))
                else:
                    medians.append((bheap[0]+-theap[0]) / 2.0)
                
                if (i == len(nums)):
                    break
                
                m, n, balance = nums[i-k], nums[i], 0
                i+=1
                
                if m >= bheap[0]:
                    balance-=1
                    if m == bheap[0]:
                        heappop(bheap)
                    else:
                        hashes[m]+=1
                else: 
                    balance+=1
                    if m == -theap[0]:
                        heappop(theap)
                    else:
                        hashes[m]+=1
                if bheap and n >= bheap[0]:  
                    balance+=1
                    heappush(bheap, n)
                else:
                    balance-=1
                    heappush(theap,-n)
                
                if balance < 0:
                    heappush(bheap,-heappop(theap))
                elif balance > 0:
                    heappush(theap, -heappop(bheap))
                    
                while bheap and hashes[bheap[0]]:
                    hashes[heappop(bheap)]-=1
                while theap and hashes[-theap[0]]:
                    hashes[-heappop(theap)]-=1
            
            return medians
    

  • 1
    A

    O.o. wow, can't believe I made that mistake. I even thought to look it up and I was like, nah I got this.

    Thanks :-)

    @zhongyuan9817


  • 1
    Z

    no worries ;)


  • 0
    W
    This post is deleted!

  • 0
    P
    This post is deleted!

  • 0
    P
    This post is deleted!

  • 3
    G

    Every time I saw your code, I feel like that you are playing the Python and I am played by Python.


Log in to reply
 

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