[LeetCode/Python] 219. Contains Duplicate II

📌 Problem

[LeetCode] 219. Contains Duplicate II

📌 Solution

Idea

Use a sliding window of size k with a set.

• The set keeps at most k recent elements.
• If the current number already exists in the set, it means a duplicate is found within distance k.
• When the window size exceeds k, remove the oldest element.

Code

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        # Sliding window with size k
        window = set()

        for i, x in enumerate(nums):
            if x in window:
                return True
            
            window.add(x)

            if len(window) > k:
                window.remove(nums[i - k])
            
        return False

Complexity

• Time Complexity: $O(n)$
• Space Complexity: $O(k)$