Watch 10 video solutions for Contains Duplicate II, a easy level problem involving Array, Hash Table, Sliding Window. This walkthrough by NeetCode has 770,501 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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: true
Example 2:
Input: nums = [1,0,1,1], k = 1 Output: true
Example 3:
Input: nums = [1,2,3,1,2,3], k = 2 Output: false
Constraints:
1 <= nums.length <= 105-109 <= nums[i] <= 1090 <= k <= 105Problem Overview: You are given an integer array nums and an integer k. The task is to check whether two equal values appear in the array such that the distance between their indices is at most k. Formally, find indices i and j where nums[i] == nums[j] and |i - j| ≤ k.
Approach 1: HashMap to Track Indices (O(n) time, O(n) space)
Iterate through the array while storing each value’s most recent index in a HashMap. When you encounter a number, check whether it already exists in the map. If it does, compute the distance between the current index and the stored index. If that distance is ≤ k, a valid duplicate pair exists and you can return true immediately. Otherwise, update the index in the map and continue scanning. Each lookup and update in the map is O(1) on average, so the full traversal runs in linear time. This approach is straightforward and works well for general cases where you want quick index lookups using a hash table.
Approach 2: Sliding Window with HashSet (O(n) time, O(k) space)
Maintain a sliding window of at most k elements using a HashSet. As you iterate through the array, check whether the current value already exists in the set. If it does, the duplicate lies within the last k indices, so return true. Otherwise insert the value into the set. When the window grows larger than k, remove the element that falls out of range (nums[i - k]). This keeps the set representing only the last k elements. The algorithm scans the array once with constant-time set operations, giving O(n) time and O(k) space. This pattern is common when solving distance-based constraints using a sliding window over an array.
Recommended for interviews: The sliding window solution is usually the cleanest because it directly models the constraint that indices must be within distance k. The HashMap approach is also accepted and demonstrates strong understanding of constant-time lookups. In interviews, candidates often mention a naive double loop (O(n * k)) first to show baseline reasoning, then optimize to the O(n) hash-based approach.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force (Check neighbors up to k) | O(n * k) | O(1) | Good for explaining baseline logic before optimization in interviews |
| HashMap to Track Indices | O(n) | O(n) | General solution when you want quick index lookups for previously seen values |
| Sliding Window with HashSet | O(n) | O(k) | Best when the constraint is based on distance between indices |