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)