# 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.

```python
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)*&#x20;

### 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.

```python
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)*&#x20;

### 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.

```python
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)*&#x20;
>
> **Space Complexity:** *O(n)*&#x20;