Contains Duplicate II
easyTime: O(n)Space: O(min(n, k))
Signals to notice
duplicate within k distancecheck if any two equal elements are ≤ k apartsliding window hash set
Brute force first
For each element, scan next k elements — O(nk).
The key insight
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).
What must stay true
The set always contains exactly the last k elements. If a duplicate falls within this window, it's detected immediately.
Easy way to go wrong
Not removing old elements — the set must stay bounded at size k to only check within-distance duplicates.