219. Contains Duplicate II - Detailed Explanation
Problem Statement
Description:
You are given an integer array nums and an integer k. Your task is to check whether there are two distinct indices i and j in the array such that:
nums[i] == nums[j](the same value appears more than once), andabs(i - j) <= k(the indices of the duplicates are at most k apart).
Example 1:
- Input:
nums = [1, 2, 3, 1],k = 3 - Output:
true - Explanation:
The value1appears at index 0 and index 3. The differenceabs(0 - 3) = 3is within the allowed range.
Example 2:
- Input:
nums = [1, 0, 1, 1],k = 1 - Output:
true - Explanation:
The value1appears at indices 2 and 3, andabs(2 - 3) = 1is within the range.
Example 3:
- Input:
nums = [1, 2, 3, 1, 2, 3],k = 2 - Output:
false - Explanation:
Although duplicates exist, the duplicates are farther apart than the allowed index distance of 2.
Constraints:
- The length of the array is between 1 and 10⁵ (or similar limits).
- Elements in
numscan be any integer. - k is a non-negative integer.
Hints
-
Hint 1:
To efficiently check for duplicates within a given range, consider using a hash-based data structure (like a HashSet or HashMap) to quickly look up whether an element has been seen within the required window. -
Hint 2:
One strategy is to maintain a sliding window of at most k elements. As you traverse the array, if the current element already exists in the window, return true. Otherwise, add the element to the window and, if the window size exceeds k, remove the element that is too far behind. -
Hint 3:
Alternatively, use a hash map that stores the last index at which each element was seen. If you encounter an element that was seen previously and the difference between the current index and the stored index is at most k, return true.
Approach 1: Sliding Window with a HashSet
Idea
The sliding window approach involves maintaining a set that represents the last k elements (indices) seen. As you iterate through the array:
-
Check if the current element exists in the set.
-
If it does, then a duplicate within k indices exists, and you return true.
-
Otherwise, add the current element to the set.
-
If the size of the set exceeds k (i.e. the current index minus the oldest index is greater than k), remove the element that is no longer in the sliding window.
This method ensures that you only keep track of elements that are within the current window of size k.
Approach 2: HashMap Storing Last Seen Indices
Idea
Another approach is to use a hash map that maps each element to its most recent index. As you traverse the array:
-
For each element, check if it exists in the hash map.
-
If it does, compare the current index with the stored index.
-
If the difference is less than or equal to k, return true.
-
Update the hash map with the current index for that element.
This method avoids maintaining an explicit window and directly checks the distance condition.
Code Implementation
Python Code (Sliding Window with HashSet)
Java Code (Using HashSet for Sliding Window)
Complexity Analysis
-
Time Complexity:
- Both approaches iterate over the array once, so the time complexity is O(n), where n is the length of
nums.
- Both approaches iterate over the array once, so the time complexity is O(n), where n is the length of
-
Space Complexity:
- The sliding window (HashSet) approach maintains at most k elements, so the space complexity is O(min(n, k)).
- The HashMap approach also has similar space complexity.
Step-by-Step Walkthrough and Visual Example
Consider nums = [1, 2, 3, 1] with k = 3 using the sliding window approach:
- Iteration 0:
i = 0, element = 1.- Set is empty; add 1 → seen = {1}.
- Iteration 1:
i = 1, element = 2.- 2 is not in seen; add 2 → seen = {1, 2}.
- Iteration 2:
i = 2, element = 3.- 3 is not in seen; add 3 → seen = {1, 2, 3}.
- Iteration 3:
i = 3, element = 1.- 1 is already in seen, and since the window size is within k, return true.
Common Mistakes and Edge Cases
Common Mistakes
-
Not Maintaining the Window Size Correctly:
Ensure that when the window size exceeds k, you remove the oldest element. Forgetting to do so can lead to false positives. -
Misinterpreting the Index Difference:
Remember that the condition requires the difference in indices to be less than or equal to k, not the number of elements between them.
Edge Cases
-
Single Element Array:
Ifnumscontains only one element, no duplicates exist, so the answer is false. -
k = 0:
Since no index can have a difference of 0 with another distinct index, the answer should be false regardless of duplicates in the array. -
All Elements Unique:
The function should return false if there are no duplicates.
Variations
-
Contains Duplicate I:
Check if any duplicates exist regardless of index differences. -
Contains Duplicate III:
A more complex variation where you must check if there are duplicates within a certain absolute difference and within a value difference.
Related Problems for Further Practice
-
Two Sum:
Use hash maps to find pairs that satisfy a condition. -
Sliding Window Maximum:
Practice maintaining a window and updating its state efficiently.
GET YOUR FREE
Coding Questions Catalog
