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: Given an integer array nums and an integer k, determine whether two distinct indices i and j exist such that nums[i] == nums[j] and the distance between them is at most k. The task is essentially detecting duplicates within a limited index range rather than across the entire array.
Approach 1: HashMap to Track Indices (O(n) time, O(n) space)
This approach uses a hash map to store the most recent index where each number appeared. Iterate through the array once. For each element nums[i], check if it already exists in the hash table. If it does, compute the distance between the current index and the stored index. If the difference is less than or equal to k, a valid duplicate pair exists and you return true. Otherwise update the stored index to the current position. The key insight: you only need the latest occurrence of each value because earlier ones produce larger index gaps. Hash lookups run in constant time, giving an overall O(n) traversal.
This method works well when you want the most straightforward implementation. The hash map directly tracks positions and avoids maintaining an explicit window structure.
Approach 2: Sliding Window with HashSet (O(n) time, O(k) space)
This approach treats the problem as maintaining a window of size at most k. Use a sliding window and a hash set that stores the values currently inside the window. Iterate through the array while expanding the window to the right. If the current value already exists in the set, you found two equal values within distance k. Add the current value to the set, and when the window grows larger than k, remove the element that falls out of the left side (nums[i - k]).
The insight here is that any valid pair must lie within the last k elements. By keeping only those elements in memory, you ensure duplicates are detected immediately while limiting memory usage. This reduces space complexity to O(k) instead of O(n).
Recommended for interviews: Both approaches run in O(n) time and demonstrate efficient use of hashing. Interviewers typically expect the sliding window or hash map optimization after discussing the naive O(n²) pair comparison. Showing the brute-force idea first proves you understand the requirement, but implementing the hash-based O(n) solution demonstrates practical algorithmic thinking and familiarity with common interview patterns.
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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 |
|---|---|---|---|
| HashMap to Track Indices | O(n) | O(n) | General case when tracking last seen index is simplest |
| Sliding Window with HashSet | O(n) | O(k) | When you want to limit memory to only the last k elements |
Contains Duplicate - Leetcode 217 - Python • NeetCode • 770,501 views views
Watch 9 more video solutions →Practice Contains Duplicate II with our built-in code editor and test cases.
Practice on FleetCode