219. Contains Duplicate II

Approach 1: Brute Force

The easiest solution is to brute force our way through for each element in the array and try to find another one close enough to satisfy our condition.

def containsNearbyDuplicate(self, nums, k): 
    """ 
    :type nums: List[int] 
    :type k: int 
    :rtype: bool 
    """ 
    for i in range(len(nums)): 
        for j in range(len(nums)): 
            if i != j and abs(i-j) <= k and nums[i] == nums[j]: 
                return True
    return False

As expected this solution exceeds the time limit at test case 22/23

Time Complexity: O(n²)

Space Complexity: O(1)

Approach 2: Sliding Window

We can take the sliding window approach by looking at the next 'k' positions in the array and looking for matches.

def containsNearbyDuplicate(self, nums, k):        
    """        
    :type nums: List[int]        
    :type k: int        
    :rtype: bool        
    """        
    window = set()        
    for i in range(0, len(nums)):            
        if len(window) >= k+1:                
            window.remove(nums[i-k-1])            
        if nums[i] in window:                
            return True            
        window.add(nums[i])        
    return False

This solution although accepted doesn't really have the best runtime, coming in at a measly 66.5% percentile.

Time Complexity: O(nk) (Lookup in sets is O(1) in Python)

Space Complexity: O(k)

Approach 3: Dictionary of last seen positions

We can iterate over the array and keep track of where we see a number, and then if we see it again, check to see if it passes the distance constraint.

def containsNearbyDuplicate(nums, k): 
    """
    :type nums: List[int] 
    :type k: int 
    :rtype: bool """ 
    dic = {}
    for i, v in enumerate(nums):    
        if v in dic and i - dic[v] <= k:        
            return True    
        dic[v] = i
    return False

As expected, this solution passes with flying colours coming in at a solid 98.3% percentile among other solutions.

Time Complexity: O(n)

Space Complexity: O(n)