Contains Duplicate II
Easy · Sliding Window · Array · Hash Table · Sliding Window
Problem
Given an integer array nums and an integer k, return true if there are two different indices i and j with nums[i] == nums[j] and |i - j| <= k, and false otherwise.
In other words: does any value repeat within a stretch of at most k + 1 consecutive positions?
Examples
Input: nums = [4,2,7,4], k = 3 Output: true
The two 4s are at indices 0 and 3, exactly 3 apart.
Input: nums = [4,2,7,4], k = 2 Output: false
The only repeat is 3 positions apart, more than k = 2.
Input: nums = [1,0,1,1], k = 1 Output: true
The 1s at indices 2 and 3 are next to each other.
Constraints
- 1 <= len(nums) <= 10^5
- -10^9 <= nums[i] <= 10^9
- 0 <= k <= 10^5
Approaches
- Baseline: compare with the next k values — time O(n · min(n, k)), space O(1)
Follow-up
What if the values only need to be close, |nums[i] - nums[j]| <= t, instead of equal? A hash set cannot answer "is anything nearby"; buckets of width t + 1 can, because two values in the same bucket are always close enough. That is the second use case below.
Related problems
Start free on Cariara · Coding problems · System design studio
