Contains Duplicate II
(#219), Easy
Category: Array, Hash Table, Sliding Window
Problem Statement
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`.
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
Approach
Brute Force
- Iterate through each index `i` from `0` to `n - 1`.
- For each index `i`, check the next `k` elements (from `i+1` to `i+k`) to see if any are equal to `nums[i]`.
- If a duplicate is found within the range, return `true`.
- If no duplicates are found in any range, return `false`.
var containsNearbyDuplicate = function(nums, k) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j <= i + k && j < nums.length; j++) {
if (nums[i] === nums[j]) return true;
}
}
return false;
};Sliding Window with Set
- Initialize an empty Set to track the elements in the current window of size `k`.
- Iterate through the array `nums` using index `i`.
- If `nums[i]` is already in the Set, return `true` (duplicate within window found).
- Otherwise, add `nums[i]` to the Set.
- If the Set size exceeds `k`, remove the element at `i - k` from the Set (to maintain the window).
- If no duplicates are found by the end of the loop, return `false`.
var containsNearbyDuplicate = function(nums, k) {
const set = new Set();
for (let i = 0; i < nums.length; i++) {
if (set.has(nums[i])) return true;
set.add(nums[i]);
if (set.size > k) {
set.delete(nums[i - k]);
}
}
return false;
};Complexity
Time: O(n)
Space: O(min(n, k))