visual walkthrough
Contains Duplicate II
A window of size k kept in a set.
The idea
Two equal numbers are "close" if their indices differ by at most k. So as you scan, you only need to remember the last k numbers: if the current one is among them, you've found a close duplicate.
A set that drops its oldest member when it grows past k does exactly that.
Complexity
| approach | time | space |
|---|---|---|
| Compare nearby pairs | O(n · k) | O(1) |
| Window of the last k | O(n) | O(k) |