Leetcode 219. Contains Duplicate II

Problem

Leetcode 219 - Contains Duplicate II

Example:

Input: nums = [1,2,3,1], k = 3
Output: true

Input: nums = [1,0,1,1], k = 1
Output: true

Input: nums = [1,2,3,1,2,3], k = 2
Output: false

Approach

We can have a window size of k+1 and make it a set, then we can check if there is a duplicate by sliding the window to len(nums)

Visualization of the Approach:

nums = [1,2,3,1], k = 3
window = ()
nums[right] = 1

window = (1)
nums[right] = 2

window = (1,2)
nums[right]= 3

window = (1,2,3)
nums[right] = 1, since there's duplicate return true

Here is the Python code for the solution:

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        window = set()
        left = 0

        for right in range(len(nums)):
            if right - left > k:
                window.remove(nums[left])
                left += 1
            
            if nums[right] in window:
                return True
            
            window.add(nums[right])
    
        return False    

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(min(n, k))$, since our window size is k at max