Contains Duplicate II(#219)
Category: Array, Hash Set, 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
Approach 1. Brute Force Approach:
• Iterate through each element in the array using index `i`.
• For each `i`, check the next `k` elements to see if any are equal to `nums[i]`.
• If found, return true.
Approach 2. Optimized Sliding Window Approach:
• Use a Set to maintain the last `k` elements we've seen.
• Loop through the array:
• If the current element is already in the Set, return true.
• Otherwise, add it to the Set.
• If the Set size exceeds `k`, remove the element that falls out of the window range.
• if no duplicates found within range `k`, return false.
💻 Code
/* Brute Force Approach */
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;
};
/* Optimized Sliding Window Approach */
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))