Contains Duplicate II
easyTime: O(n)Space: O(min(n, k))
Recognize the pattern
duplicate within k distancecheck if any two equal elements are ≤ k apartsliding window hash set
Brute force idea
For each element, scan next k elements — O(nk).
Better approach
Maintain a hash set of the last k elements. If new element is in the set, return true. If set size > k, remove the oldest. O(n).
Key invariant
The set always contains exactly the last k elements. If a duplicate falls within this window, it's detected immediately.
Watch out for
Not removing old elements — the set must stay bounded at size k to only check within-distance duplicates.