Contains Duplicate II
Contains Duplicate II: decide whether the array holds two equal values whose indices differ by at most k. Duplicates further apart than k do not count.
- 1 <= nums.length <= 10⁵
- -10⁹ <= nums[i] <= 10⁹
- 0 <= k <= 10⁵
Intuition
Only the most recent occurrence of a value can ever satisfy the distance bound, because any earlier one is strictly further away. So there is no need to remember every position of every value — a map from value to its latest index is enough. On each element, compare against that stored index and update it, which decides the whole question in one pass.
A constraint of the form within k positions turns a global question into a local one, and local questions want either a sliding window or a last-seen map. The tell is a distance bound between two indices rather than a condition on the values themselves.
Approach
Before reading on: convince yourself that storing only the most recent index of each value never loses a valid answer. Then check what happens if you skip the overwrite when a duplicate is found but is too far away.
Why the latest occurrence is the only one worth keeping
Suppose value v appeared at indices 2 and 7, and you now stand at index 9. The gap to 7 is 2 and the gap to 2 is 7 — the earlier occurrence is always the worse candidate. Formally, for a fixed current index i, the distance i - j shrinks as j grows, so the largest stored j minimises it. Any occurrence that fails the test from the most recent position would fail from an older one too, which is what licenses discarding history and storing a single index per value.
One pass with a last-seen map
Walk the array holding a dictionary last mapping value to the index where it was most recently seen. At index i with value v, if v is in the map and i - last[v] <= k, a qualifying pair exists and the answer is true immediately. Otherwise write last[v] = i, overwriting any older index. The overwrite is not an optimisation but a correctness step: keeping the stale index would compare future elements against a position that is no longer the nearest one.
The sliding-window view and its cost
An equivalent formulation keeps a set of the last k values and asks whether the current element is already inside it, removing the element that falls out of range as the window advances. Both run in O(n) time; the set version caps memory at O(min(n, k)) while the map version can hold up to O(n) distinct values. The map is simpler to write correctly because it needs no eviction step, and eviction is where the window version usually goes wrong — forgetting it lets stale values match across a gap larger than k.
Solution & live demo
Common pitfalls
Not overwriting the index after a failed distance check
if num in last:
if i - last[num] <= k:
return True
else:
last[num] = iif num in last and i - last[num] <= k:
return True
last[num] = iWhen a duplicate is too far away the stored index must still advance. Leaving the old one means later elements are measured against a stale position and a genuinely close pair is missed — [1,2,1,1] with k = 1 wrongly returns false.
Comparing values rather than index distance
if num in last:
return Trueif num in last and i - last[num] <= k:
return TrueThis answers Contains Duplicate I instead. It ignores k entirely and returns true for any repeat, however far apart the two occurrences are.
Using a strict inequality on the bound
if i - last[num] < k:
if i - last[num] <= k:
The problem says abs(i - j) <= k, so a gap of exactly k qualifies. The strict version rejects the boundary case, failing on [1,0,1] with k = 2.
Edge cases
No two distinct indices can differ by at most 0, so the answer is always false.
The bound is inclusive, so i - j == k qualifies and returns true.
The test fails, but the index is still overwritten so later pairs are measured correctly.
Every value is written once and the loop finishes with false.
Overwriting keeps the nearest index, so the qualifying pair is still found.