Contains Duplicate II solution and explanation
TCS
Google
9 more videos on this problem
Contains Duplicate II - Leetcode 219 - PythonNeetCodeIO · 5:27 · 86K views
219. Contains Duplicate II | LEETCODE EASYcode Explainer · 7:07 · 13K views
Leetcode | 219. Contains Duplicate II | Easy | Java SolutionDeveloper Docs · 6:02 · 5K views
LeetCode 219 | Contains Duplicate IIEngineering Digest · 10:34 · 5K views
Contains Duplicate II | LeetCode 219 | Google Coding Interview TutorialTerrible Whiteboard · 9:12 · 5K views
Contains Duplicate II LeetCode 219 | Intuitive Explanation + CodeCodingNinja · 13:30 · 5K views
LeetCode 217 & 219: Contains Duplicate I & II - Interview Prep Ep 46Fisher Coder · 18:11 · 4K views
Contains Duplicate II | LeetCode 219 (Sliding Window)Destination FAANG · 12:52 · 3K views
Contains Duplicate II - LeetCode 219 - Python #leetcodeDeepti Talesra · 5:30 · 3K views
219. Contains Duplicate II | LeetCode SolutionGame of Coders · 5:07 · 3K views
The problem
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.
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
index_map = {}
for i, number in enumerate(nums):
if number in index_map and i - index_map[number] <= k:
return True
index_map[number] = i
return Falseimport java.util.HashMap;
public class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(nums[i]) && i - map.get(nums[i]) <= k) {
return true;
}
map.put(nums[i], i);
}
return false;
}
}#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_map<int, int> map;
for (int i = 0; i < nums.size(); ++i) {
if (map.count(nums[i]) && i - map[nums[i]] <= k) {
return true;
}
map[nums[i]] = i;
}
return false;
}
};var containsNearbyDuplicate = function(nums, k) {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
if (map.has(nums[i]) && (i - map.get(nums[i]) <= k)) {
return true;
}
map.set(nums[i], i);
}
return false;
};#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
struct HashMap {
int* keys;
int* values;
int size;
int capacity;
};
struct HashMap* createHashMap(int capacity) {
struct HashMap* map = (struct HashMap*)malloc(sizeof(struct HashMap));
map->keys = (int*)malloc(sizeof(int) * capacity);
map->values = (int*)malloc(sizeof(int) * capacity);
map->size = 0;
map->capacity = capacity;
return map;
}
void destroyHashMap(struct HashMap* map) {
free(map->keys);
free(map->values);
free(map);
}
int hashFindIndex(struct HashMap* map, int key) {
for (int i = 0; i < map->size; i++) {
if (map->keys[i] == key) {
return i;
}
}
return -1;
}
void hashInsert(struct HashMap* map, int key, int value) {
if (map->size < map->capacity) {
map->keys[map->size] = key;
map->values[map->size] = value;
map->size++;
}
}
bool containsNearbyDuplicate(int* nums, int numsSize, int k) {
struct HashMap* map = createHashMap(numsSize);
for (int i = 0; i < numsSize; i++) {
int index = hashFindIndex(map, nums[i]);
if (index != -1 && i - map->values[index] <= k) {
destroyHashMap(map);
return true;
}
if (index != -1) {
map->values[index] = i;
} else {
hashInsert(map, nums[i], i);
}
}
destroyHashMap(map);
return false;
}using System;
using System.Collections.Generic;
public class Solution {
public bool ContainsNearbyDuplicate(int[] nums, int k) {
Dictionary<int, int> map = new Dictionary<int, int>();
for (int i = 0; i < nums.Length; i++) {
if (map.ContainsKey(nums[i]) && i - map[nums[i]] <= k) {
return true;
}
map[nums[i]] = i;
}
return false;
}
}The Python code relies on a dictionary to maintain a relationship between array elements and their indices. At each iteration, the method verifies if the current number already appears within the allowed distance, consequently updating the index in the dictionary.
Time Complexity: O(n), where n is the size of the 'nums' array, owing to O(1) average complexity for dictionary lookup and insertion operations.
Space Complexity: O(min(n, k)), determined by the limited size of the dictionary, which holds at most k elements simultaneously.
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.
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
window = set()
for i, number in enumerate(nums):
if i > k:
window.remove(nums[i - k - 1])
if number in window:
return True
window.add(number)
return Falseimport java.util.HashSet;
import java.util.Set;
public class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> window = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
if (i > k) window.remove(nums[i - k - 1]);
if (!window.add(nums[i])) return true;
}
return false;
}
}#include <unordered_set>
#include <vector>
using namespace std;
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_set<int> window;
for (int i = 0; i < nums.size(); ++i) {
if (i > k) window.erase(nums[i - k - 1]);
if (!window.insert(nums[i]).second) return true;
}
return false;
}
};var containsNearbyDuplicate = function(nums, k) {
let window = new Set();
for (let i = 0; i < nums.length; i++) {
if (i > k) window.delete(nums[i - k - 1]);
if (window.has(nums[i])) return true;
window.add(nums[i]);
}
return false;
};#include <stdbool.h>
#include <stdlib.h>
bool containsNearbyDuplicate(int* nums, int numsSize, int k) {
int* hashset = (int*) malloc(numsSize * sizeof(int));
int start = 0;
for (int i = 0; i < numsSize; ++i) {
for (int j = start; j < i; ++j) {
if (nums[i] == nums[j]) {
free(hashset);
return true;
}
}
hashset[i] = nums[i];
if (i - start >= k)
++start;
}
free(hashset);
return false;
}using System;
using System.Collections.Generic;
public class Solution {
public bool ContainsNearbyDuplicate(int[] nums, int k) {
HashSet<int> window = new HashSet<int>();
for (int i = 0; i < nums.Length; i++) {
if (i > k) window.Remove(nums[i - k - 1]);
if (!window.Add(nums[i])) return true;
}
return false;
}
}This sample renders Python's set, implementing an efficient sliding window. Post-exit, window size is maintained at k or below via element removal, allowing examination of relatively fresh entries, revalidating whether number exists therein.
Time Complexity: O(n), distributing constant time complexity across contained operations.
Space Complexity: O(min(n, k)), closely aligning potential set-storage peaks relative to encountered primary elements.
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.
function containsNearbyDuplicate(nums: number[], k: number): boolean {
const d: Map<number, number> = new Map();
for (let i = 0; i < nums.length; ++i) {
if (d.has(nums[i]) && i - d.get(nums[i])! <= k) {
return true;
}
d.set(nums[i], i);
}
return false;
}func containsNearbyDuplicate(nums []int, k int) bool {
d := map[int]int{}
for i, x := range nums {
if j, ok := d[x]; ok && i-j <= k {
return true
}
d[x] = i
}
return false
}class Solution {
/**
* @param Integer[] $nums
* @param Integer $k
* @return Boolean
*/
function containsNearbyDuplicate($nums, $k) {
$d = [];
for ($i = 0; $i < count($nums); ++$i) {
if (array_key_exists($nums[$i], $d) && $i - $d[$nums[$i]] <= $k) {
return true;
}
$d[$nums[$i]] = $i;
}
return false;
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using a HashMap to Track Indices | Time Complexity: O(n), where n is the size of the 'nums' array, owing to O(1) average complexity for dictionary lookup and insertion operations. Space Complexity: O(min(n, k)), determined by the limited size of the dictionary, which holds at most k elements simultaneously. |
| Sliding Window | Time Complexity: O(n), distributing constant time complexity across contained operations. Space Complexity: O(min(n, k)), closely aligning potential set-storage peaks relative to encountered primary elements. |
| Hash Table | – |
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 |
Frequently asked questions
Is Contains Duplicate II easy or hard?
Contains Duplicate II is classified as an Easy problem on LeetCode with an acceptance rate around 50%. The challenge focuses on recognizing the sliding window or hash-based pattern rather than complex algorithms.
Contains Duplicate II Python/Java solution
Python implementations typically use a dictionary or set, while Java solutions use HashMap or HashSet. Both languages support constant-time average lookup and insertion, enabling the optimal O(n) algorithm.
How to solve Contains Duplicate II in O(n)?
Traverse the array while maintaining a hash-based structure. With a HashMap, store the last index of each value and check if the index difference is ≤ k. With a sliding window set, maintain at most k recent elements and check for duplicates before inserting the current value.
What is the best approach for Contains Duplicate II?
The sliding window with a HashSet is typically considered the best approach. It keeps track of the last k elements while scanning the array once. If a number already exists in the window, a duplicate within distance k is found. This method runs in O(n) time and uses O(k) space.
Is Contains Duplicate II asked at Google/Amazon/Meta?
Contains Duplicate II appears frequently in interview prep lists and has been reported in interviews at companies like Amazon and other large tech firms. It tests understanding of hash tables, sliding window patterns, and efficient duplicate detection in arrays.
What data structure is used in Contains Duplicate II?
The problem is typically solved using a HashMap or HashSet. A HashMap stores each value with its last seen index, while a HashSet is used in the sliding window approach to track elements within the last k positions.
What is the time complexity of Contains Duplicate II?
The optimal solutions run in O(n) time because the array is traversed once and each element is inserted and checked in a hash-based structure in constant time. The sliding window uses O(k) space, while the HashMap approach may use up to O(n) space depending on the number of unique elements.