Contains Duplicate II - Solution & Explanation
Problem Statement
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 <= 105
Approach Overview
Problem 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 1: Using a HashMap to Track Indices
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.
Complexity
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.
Approach 2: Sliding Window
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.
Complexity
Time Complexity: O(n*k), as each number is recalculated through prior windows.
Space Complexity: O(k), correlating with the contiguous window used.
Approach 3: Hash Table
We use a hash table d to store the recently traversed numbers and their corresponding indices.
Traverse the array nums. For the current element nums[i], if it exists in the hash table and the difference between the indices is no more than k, return true. Otherwise, add the current element to the hash table.
After traversing, return false.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
Code
Python
Java
C++
Go
TypeScript
JavaScript
C#
PHP
Complexity Comparison
| 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. |
| Hash Table | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Contains Duplicate II - Leetcode 219 - Python • NeetCodeIO • 86,543 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Contains Duplicate II easy or hard?
Contains Duplicate II Python/Java solution
How to solve Contains Duplicate II in O(n)?
What is the best approach for Contains Duplicate II?
Is Contains Duplicate II asked at Google/Amazon/Meta?
What data structure is used in Contains Duplicate II?
What is the time complexity of Contains Duplicate II?
Ready to solve this problem?
Practice Contains Duplicate II with our built-in code editor and test cases.
Practice on FleetCode