219. Contains Duplicate II
Model: qwen2.5-coder:14b
Topics: Array,Hash Table
FAANG asked: 1
Acceptance rate: 38.8%
Problem Breakdown
The problem asks us to determine if there are two distinct indices i and j in an integer array nums such that the values at these indices are equal (nums[i] == nums[j]) and the absolute difference between the indices is less than or equal to a given integer k (abs(i - j) <= k). The inputs are the array nums and the integer k. The output should be a boolean value: true if such indices exist, otherwise false.
Implicit constraints include:
- The array can contain duplicate values.
- The array can have negative numbers.
- The array length is between 1 and (10^5).
- The value of
kis between 0 and (10^5).
Edge cases to consider:
- An empty array should return
false. - If
kis 0, the only way to satisfy the condition is if there are duplicate values at the same index, which is not possible. - Large arrays with many duplicates.
Intuition
A brute-force approach would involve checking every pair of indices (i, j) where j > i and verifying if nums[i] == nums[j] and abs(i - j) <= k. This approach has a time complexity of (O(n^2)), which is inefficient for large arrays.
The key insight to improve this solution is to use a hash table (dictionary in Python) to keep track of the most recent index where each value was seen. By doing so, we can check in constant time if a duplicate exists within the required distance k.
Approach
- Initialize an empty dictionary
index_mapto store the last seen index of each number. - Iterate through the array
numsusing an indexi. - For each element
numat indexi:- Check if
numis already inindex_mapand if the difference between the current indexiand the stored index is less than or equal tok.- If true, return
true.
- If true, return
- Update the dictionary with the current index
ifor the numbernum.
- Check if
- If no such pair of indices is found by the end of the iteration, return
false.
This approach ensures that each element is processed only once, leading to a linear time complexity.
Complexity Analysis
- Time Complexity: (O(n)), where (n) is the length of the array
nums. Each element is processed at most twice (once when added to the dictionary and once when checked). - Space Complexity: (O(min(n, k))). In the worst case, all elements are stored in the dictionary. However, since we only need to keep track of the last
kindices for each number, the space complexity is limited byk.
Solution
def containsNearbyDuplicate(nums, k):
index_map = {}
for i, num in enumerate(nums):
if num in index_map and i - index_map[num] <= k:
return True
index_map[num] = i
return False
Edge Cases Handled
- Empty Array: The loop will not execute, and the function will return
false. - k = 0: Since we only update the dictionary when a duplicate is found within distance
k, this case is naturally handled. - Large Arrays with Many Duplicates: The solution efficiently handles large inputs by maintaining a limited-size dictionary.