Python O(n) window sliding algorithm


  • 0
    M

    I'm just saying that we can do this, doesn't mean this solution is optimal. Just use a dictionary check and update indices should be much simpler.

    class Solution(object):
        def containsNearbyDuplicate(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: bool
            """
            if not nums or len(nums) == 0:
                return False
            table = {}
            left = 0
            right = 0
            while right < len(nums):
                if nums[right] in table:
                    return True
                table[nums[right]] = 1
                right += 1
                if right - left == k + 1: # window size == k + 1
                    del table[nums[left]]
                    left += 1
            return False
    

Log in to reply
 

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