Python O(n) time O(1) space solution beats 97%


  • 0
    S

    The idea is to have a pointer (I call max_idx) for the maximum number so far in the current window. For the first k-1 numbers, you simply assign max_idx to the cell with the maximum number. For the remaining numbers, you first check if max_idx is out of your window size, then you search for the current maximum number. The best case for this search is O(1) and the worst case is O(k).

        def maxSlidingWindow(self, nums, k):
            if not nums:
                return []
            
            res = []
            
            max_idx = 0
            for i, n in enumerate(nums):
                if i < k-1:
                    if nums[max_idx] < n:
                        max_idx = i
                else:
                    if max_idx < i-k+1:
                        max_idx = i-k+1
                        for j in xrange(max_idx, i, 1):
                            if nums[j] > nums[max_idx]:
                                max_idx = j
                    if nums[max_idx] < n:
                        max_idx = i
                    res.append(nums[max_idx])
                    
            return res
    

Log in to reply
 

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