Contains Duplicate II
The key idea
You only care about the most recent index where each value appeared. As you scan left to right, keep a map from value to its last-seen index. When you hit a value again, the closest earlier copy is the one you stored, so checking
i - last[value] <= k against that single index is enough — you never need to remember older copies.Problem
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 are looking for a repeated value whose two occurrences sit no more than k positions apart. If no such pair exists, return false.
Note that the values themselves can be large or negative, but only their positions matter for the distance check — the equal values must be close enough in the array, not close in value.
Constraints
1 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^90 <= k <= 10^5
Examples
Input: nums = [1,2,3,1], k = 3
Output: true
Input: nums = [1,0,1,1], k = 1
Output: true
Input: nums = [1,2,3,1,2,3], k = 2
Output: false
Complexity
Time: O(n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Hash Map / Set problems
- 4Sum IIMEDIUM
- Contains DuplicateEASY
- Determine if Two Strings Are CloseMEDIUM
- First Missing PositiveHARD
- Equal Row and Column PairsMEDIUM
- Find the Difference of Two ArraysEASY
- Group AnagramsMEDIUM
- Intersection of Two ArraysEASY
- Isomorphic StringsEASY
- Longest Consecutive SequenceMEDIUM
- Longest PalindromeEASY
- Majority Element IIMEDIUM