Given an integer array nums and an integer k, return true if there are two different indices i and j with nums[i] == nums[j] and |i - j| <= k.
Walk the array once and remember the last index where each value appeared. When you see a value again, check whether the gap is at most k.
def containsNearbyDuplicate(nums, k):
last = {}
for i, x in enumerate(nums):
if x in last and i - last[x] <= k:
return True
last[x] = i
return False
Keep a set of the previous k elements. Before adding nums[i], check membership; after adding, remove nums[i - k] once the window grows past k. This caps memory at O(min(n, k)), which is a nice point to raise when the interviewer asks about space.
Both versions are O(n) time.
Edge case: k = 0 can never be true, since the indices must differ.
Follow-up: Contains Duplicate III (LeetCode 220) adds a value tolerance and is usually solved with buckets.
Disclosure: I work on an AI coding interview assistant at Linkjob AI, and I write these notes while practicing.
Further reading: Linkjob AI resource directory