Contains Duplicate II
Problem Statement
Given an integer array nums and an integer k, return true if there are two distinct indices i and j such that nums[i] == nums[j] and abs(i - j) <= k. Otherwise, return false.
Input
An integer array nums and an integer k, the maximum allowed distance between duplicate values.
Output
A boolean: true if any duplicate pair appears within distance k, otherwise false.
Constraints
- •
1 <= nums.length <= 10^5 - •
-10^9 <= nums[i] <= 10^9 - •
0 <= k <= 10^5
Examples
Example 1
nums = [1,2,3,1], k = 3
trueExample 2
nums = [1,0,1,1], k = 1
trueExample 3
nums = [1,2,3,1,2,3], k = 2
falseLearning Objectives
- Reframe the distance condition as a fixed window of the last **k** indices.
- Use a HashSet to test whether the current value already appears in that window.
- Remove the leaving value so the set never represents indices too far away.
- Handle **k = 0** without creating a false duplicate match.
Intuition
The pattern signal is the bound abs(i - j) <= k. For a current index j, only the previous k indices can form a valid pair with it. Anything farther left is irrelevant and must not remain in the active window.
A wasteful approach compares each index with up to k previous indices. Sliding window turns that range of previous indices into a set. If the current value is already in the set, a valid nearby duplicate exists. If not, add it and remove the value that falls more than k positions behind.
Common mistakes
- ×Keeping every value ever seen, which solves Contains Duplicate but ignores the distance limit.
- ×Removing the leaving value before checking the current value when the intended window is the previous **k** indices.
- ×Forgetting that **k = 0** can never produce distinct indices within distance zero.
- ×Using a set but allowing it to grow beyond **k** elements, which can report duplicates that are too far apart.
Algorithm Explanation
Window setup
Maintain a HashSet named window containing values from the previous at most k indices. Before processing nums[right], the set represents exactly the values that are close enough to pair with right.
Window visualization
For nums = [1,2,3,1] and k = 3, start with an empty window. At index 0, 1 is not present, so add it. At index 1, the window is [1] and 2 is new, so add it. At index 2, the window is [1,2] and 3 is new, so add it. At index 3, the window is [1,2,3] and the entering value 1 is already present. That duplicate is within the last 3 indices, so return true.
Algorithm
- Create an empty HashSet for the active window.
- Scan nums from left to right with index right.
- If nums[right] is already in the set, return true.
- Add nums[right] to the set.
- If the set now contains more than k indices worth of values, remove nums[right - k] because it will be too far away for the next index.
- If the scan finishes without a match, return false.
Solutions
Solution: HashSet of the last k values
Keep only the values whose indices are close enough to the current index. The set gives O(1) average lookup for whether the current value has appeared within the last k positions.
Step-by-step
- Create an empty HashSet named window.
- For each index right, first check whether nums[right] is already in window.
- If it is present, return true because the matching index is within the previous k positions.
- Add the current value to the window.
- When the window grows beyond k values, remove the value at right - k so future checks cannot match an index that is too far away.
- Return false after scanning every element.
O(n)
O(min(n, k))
Each value is added once, removed at most once, and looked up once in the HashSet.
Java implementation
Dry Run
Sample input
nums = [1,2,3,1], k = 3. The active set contains values from the previous at most three indices before checking the current value.
| index | incoming value | window before check | decision | window after step |
|---|---|---|---|---|
| 0 | 1 | empty | 1 is not present, so add it. | [1] |
| 1 | 2 | [1] | 2 is not present, so add it. | [1,2] |
| 2 | 3 | [1,2] | 3 is not present, so add it. | [1,2,3] |
| 3 | 1 | [1,2,3] | 1 is already present, so return true. | match found |
At index 3, the value 1 matches index 0, and 3 - 0 = 3, which satisfies k = 3.
Interview Tips
Explain the set as a distance filter, not just a duplicate detector. The current index only cares about the previous k positions, so removing stale values is what makes the answer respect the distance constraint. If asked for an alternative, mention a HashMap from value to latest index; it also runs in O(n), but the fixed-window set mirrors the pattern more directly.
Likely follow-ups
- How would you return the duplicate pair of indices instead of a boolean?
- How would you solve it with a HashMap of latest indices?
- How would the solution change if values arrived as a stream?
- How would you count all nearby duplicate pairs rather than stopping at the first one?
Similar Problems
Key Takeaways
- The distance limit **k** means only the previous **k** indices matter.
- A HashSet turns duplicate lookup inside that active window into O(1) average time.
- Removing stale values is essential; otherwise the solution ignores the distance constraint.
- For **k = 0**, the window is always empty before each check, so no distinct pair can match.