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.
This approach utilizes a hash map (dictionary) to maintain a mapping between array elements and their indices. As we iterate through the array, we check if the current element already exists in the hash map. If it does, we calculate the difference between the current index and the stored index and check if it is less than or equal to k. If this condition is met, we return true. Otherwise, we update the hash map with the current index for the element.
The C implementation uses a simple linear probing method to find existing entries and update them if necessary. It involves creating a custom hash map structure with keys and values to store elements and their indices. The solution updates the index of previously seen elements and continuously checks the difference between indices.
Time Complexity: O(n), where n is the number of elements in the array, since each insert/find operation is linear.
Space Complexity: O(min(n, k)), where n is the number of elements in the array, because we store at most k elements in the map at any time.
This method employs a sliding window (of length k) to automatically invalidate indices of prior numbers as the window advances through the array. The structure operates similarly to a hash set within the k-restricted scope, resulting in more direct checks and validations during index alterations.
A simplistic rendition of the sliding window technique stems within this C solution, resetting the start within each traversal whilst observing whether the window eventually surpasses k. Hashset components store only within their boundary, consequently alleviating redundant checks.
Time Complexity: O(n*k), as each number is recalculated through prior windows.
Space Complexity: O(k), correlating with the contiguous window used.
| Approach | Complexity |
|---|---|
| Using a HashMap to Track Indices | Time Complexity: O(n), where n is the number of elements in the array, since each insert/find operation is linear. Space Complexity: O(min(n, k)), where n is the number of elements in the array, because we store at most k elements in the map at any time. |
| Sliding Window | Time Complexity: O(n*k), as each number is recalculated through prior windows. Space Complexity: O(k), correlating with the contiguous window used. |
| 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 |
Contains Duplicate II - Leetcode 219 - Python • NeetCodeIO • 79,979 views views
Watch 9 more video solutions →Practice Contains Duplicate II with our built-in code editor and test cases.
Practice on FleetCode