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.

defcontainsNearbyDuplicate(self, nums, k):

"""

:type nums: List[int]

:type k: int

:rtype: bool

"""

for i inrange(len(nums)):

for j inrange(len(nums)):

if i != j andabs(i-j)<= k and nums[i]== nums[j]:

returnTrue

returnFalse

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.

defcontainsNearbyDuplicate(self, nums, k):

"""

:type nums: List[int]

:type k: int

:rtype: bool

"""

window =set()

for i inrange(0,len(nums)):

iflen(window)>= k+1:

window.remove(nums[i-k-1])

if nums[i]in window:

returnTrue

window.add(nums[i])

returnFalse

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.

defcontainsNearbyDuplicate(nums, k):

"""

:type nums: List[int]

:type k: int

:rtype: bool """

dic ={}

for i, v inenumerate(nums):

if v in dic and i - dic[v]<= k:

returnTrue

dic[v]= i

returnFalse

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