DSA problem
Contains Duplicate II
Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.
In other words, you must decide whether any value repeats within a window of at most k positions. A hash map that stores the most recent index of each value lets you answer this in a single pass: whenever you revisit a value, compare the current index with its last seen index.
Examples
Example 1
Input:
nums = [1,2,3,1], k = 3Output:
trueExplanation: The value 1 appears at indices 0 and 3, and abs(0 - 3) = 3 which is within k = 3.
Example 2
Input:
nums = [1,0,1,1], k = 1Output:
trueExplanation: The value 1 appears at indices 2 and 3, and abs(2 - 3) = 1 which is within k = 1.
Example 3
Input:
nums = [1,2,3,1,2,3], k = 2Output:
falseExplanation: Every repeated value is at least 3 indices apart, which exceeds k = 2, so no valid pair exists.
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- 0 <= k <= 10^5
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.