219_contains_nearby_duplicate_II.py

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        n = len(nums)

        # approach-1: brute force
        # for i in range(n-1):
        #     for j in range(i+1, n):
        #         if abs(i-j) <= k and nums[i] == nums[j]:
        #             return True

        # return False

        # approach-2: sliding window
        elements = set()
        
        # preapre the intial set
        s = min(k+1, n)
        for i in range(s):
            if nums[i] in elements:
                return True
            elements.add(nums[i])

        # set the lower and upper bound
        l = 0 
        u = k
        while u < len(nums)-1:
            elements.remove(nums[l])
            l += 1

            u += 1
            if nums[u] in elements:
                return True
            elements.add(nums[u])
        
        return False