Contains Duplicate II
EasyPrompt
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.
Example 1:
Input: nums = [1,2,3,1], k = 3
Output: trueExample 2:
Input: nums = [1,0,1,1], k = 1
Output: trueExample 3:
Input: nums = [1,2,3,1,2,3], k = 2
Output: false
Constraints:
1 <= nums.length <= 105-109 <= nums[i] <= 1090 <= k <= 105
Approaches
3 approaches with complexity analysis and trade-offs.
Use a HashMap to store the most recent index of each element and check for distance constraint.
Algorithm
- Create a HashMap to store element to index mapping
- Iterate through the array
- If current element exists in map and distance ≤ k, return true
- Update element's index in map
- If loop completes, return false
Walkthrough
We use a HashMap to store each element as key and its most recent index as value. For each element, we check if it exists in the map and if the distance from its last occurrence is within k. If yes, we found a valid duplicate. Otherwise, we update the element's most recent index in the map.
public boolean containsNearbyDuplicate(int[] nums, int k) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { if (map.containsKey(nums[i])) { if (i - map.get(nums[i]) <= k) { return true; } } map.put(nums[i], i); } return false;}Complexity
Time
O(n) where n is the length of array as we only traverse the array once
Space
O(n) in worst case where all elements are unique
Trade-offs
Pros
Most efficient solution
Single pass through array
No need to remove elements
Cleaner implementation
Cons
Uses more space than sliding window approach
HashMap operations have some overhead
Space complexity doesn't benefit from k constraint
Compare each element with all elements within k distance ahead of it to find duplicates.
Algorithm
- Iterate through the array with index i from 0 to n-1
- For each i, check elements from i+1 to min(i+k, n-1)
- If any element matches nums[i], return true
- If no matches found, return false
Walkthrough
For each element at index i, we check all elements from index i+1 up to i+k (or the end of array) to find if there's a matching element. If we find a match and the indices difference is less than or equal to k, we return true.
public boolean containsNearbyDuplicate(int[] nums, int k) { for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j <= Math.min(i + k, nums.length - 1); j++) { if (nums[i] == nums[j]) { return true; } } } return false;}Complexity
Time
O(n*k) where n is the length of array and k is the given window size
Space
O(1) as we only use constant extra space
Trade-offs
Pros
Simple to implement
No extra space required
Works well for small arrays and small k values
Cons
Very inefficient for large arrays
Redundant comparisons
Time complexity increases linearly with k
Use a HashSet to maintain elements in the current window of size k and check for duplicates.
Algorithm
- Create a HashSet to store elements in current window
- Iterate through the array
- If current index > k, remove element at (i-k-1) from set
- Try to add current element to set
- If addition fails (element already exists), return true
- If loop completes, return false
Walkthrough
We use a HashSet to store elements in the current window. For each element, we first remove elements that are outside the window (i.e., beyond k positions back), then check if current element exists in the set. If it does, we found a duplicate within k distance. If not, add the current element to the set.
public boolean containsNearbyDuplicate(int[] nums, int k) { Set<Integer> window = new HashSet<>(); for (int i = 0; i < nums.length; i++) { if (i > k) { window.remove(nums[i - k - 1]); } if (!window.add(nums[i])) { return true; } } return false;}Complexity
Time
O(n) where n is the length of array as we only traverse the array once
Space
O(min(k,n)) as we store at most k+1 elements in the HashSet
Trade-offs
Pros
More efficient than brute force
Maintains only k elements in memory at a time
O(1) lookup time for duplicates
Cons
Uses extra space proportional to window size
Requires removing elements from set
HashSet operations have some overhead
Solutions
Solution
public class Solution { public bool ContainsNearbyDuplicate ( int [] nums , int k ) { var d = new Dictionary < int , int >(); for ( int i = 0 ; i < nums . Length ; ++ i ) { if ( d . ContainsKey ( nums [ i ]) && i - d [ nums [ i ]] <= k ) { return true ; } d [ nums [ i ]] = i ; } return false ; } }class Solution {public boolean containsNearbyDuplicate(int[] nums, int k) { Map<Integer, Integer> d = new HashMap<>(); for (int i = 0; i < nums.length; ++i) { if (i - d.getOrDefault(nums[i], -1000000) <= k) { return true; } d.put(nums[i], i); } return false; }}/** * @param {number[]} nums * @param {number} k * @return {boolean} */ var containsNearbyDuplicate = function (nums, k) { const d = new Map(); for (let i = 0; i < nums.length; ++i) { if (d.has(nums[i]) && i - d.get(nums[i]) <= k) { return true; } d.set(nums[i], i); } return false; };class Solution {public: bool containsNearbyDuplicate(vector<int> &nums, int k) { unordered_map<int, int> d; for (int i = 0; i < nums.size(); ++i) { if (d.count(nums[i]) && i - d[nums[i]] <= k) { return true; } d[nums[i]] = i; } return false; }};class Solution: def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool: mp = {} for i, v in enumerate(nums): if v in mp and i - mp[v] <= k: return True mp[v] = i return FalseVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.