# Contains Duplicate II
**Difficulty:** EASY
[External](https://leetcode.com/problems/contains-duplicate-ii)
Canonical: https://scaleengineer.com/dsa/problems/contains-duplicate-ii
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Array, Hash Table
**Companies:** [Airbnb](https://scaleengineer.com/companies/airbnb), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Google](https://scaleengineer.com/companies/google), [Netflix](https://scaleengineer.com/companies/netflix), [Arista Networks](https://scaleengineer.com/companies/arista-networks), [Palantir Technologies](https://scaleengineer.com/companies/palantir-technologies)
---
## 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] <= 109`
* `0 <= k <= 105`

# Approaches
## Brute Force Approach
Compare each element with all elements within k distance ahead of it to find duplicates.
**Time:** O(n*k) where n is the length of array and k is the given window size · **Space:** O(1) as we only use constant extra space
**Pros:** Simple to implement; No extra space required; Works well for small arrays and small k values
**Cons:** Very inefficient for large arrays; Redundant comparisons; Time complexity increases linearly with k
### Explanation
For each element at index i, we check all elements from index i+1 up to i+k (or the end of array) to find if there's a matching element. If we find a match and the indices difference is less than or equal to k, we return true.

```java
public boolean containsNearbyDuplicate(int[] nums, int k) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j <= Math.min(i + k, nums.length - 1); j++) {
            if (nums[i] == nums[j]) {
                return true;
            }
        }
    }
    return false;
}
```
### Algorithm
1. Iterate through the array with index i from 0 to n-1
2. For each i, check elements from i+1 to min(i+k, n-1)
3. If any element matches nums[i], return true
4. If no matches found, return false

## Sliding Window with HashSet
Use a HashSet to maintain elements in the current window of size k and check for duplicates.
**Time:** O(n) where n is the length of array as we only traverse the array once · **Space:** O(min(k,n)) as we store at most k+1 elements in the HashSet
**Pros:** More efficient than brute force; Maintains only k elements in memory at a time; O(1) lookup time for duplicates
**Cons:** Uses extra space proportional to window size; Requires removing elements from set; HashSet operations have some overhead
### Explanation
We use a HashSet to store elements in the current window. For each element, we first remove elements that are outside the window (i.e., beyond k positions back), then check if current element exists in the set. If it does, we found a duplicate within k distance. If not, add the current element to the set.

```java
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;
}
```
### Algorithm
1. Create a HashSet to store elements in current window
2. Iterate through the array
3. If current index > k, remove element at (i-k-1) from set
4. Try to add current element to set
5. If addition fails (element already exists), return true
6. If loop completes, return false

## HashMap with Index Tracking
Use a HashMap to store the most recent index of each element and check for distance constraint.
**Time:** O(n) where n is the length of array as we only traverse the array once · **Space:** O(n) in worst case where all elements are unique
**Pros:** Most efficient solution; Single pass through array; No need to remove elements; Cleaner implementation
**Cons:** Uses more space than sliding window approach; HashMap operations have some overhead; Space complexity doesn't benefit from k constraint
### Explanation
We use a HashMap to store each element as key and its most recent index as value. For each element, we check if it exists in the map and if the distance from its last occurrence is within k. If yes, we found a valid duplicate. Otherwise, we update the element's most recent index in the map.

```java
public boolean containsNearbyDuplicate(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    
    for (int i = 0; i < nums.length; i++) {
        if (map.containsKey(nums[i])) {
            if (i - map.get(nums[i]) <= k) {
                return true;
            }
        }
        map.put(nums[i], i);
    }
    return false;
}
```
### Algorithm
1. Create a HashMap to store element to index mapping
2. Iterate through the array
3. If current element exists in map and distance ≤ k, return true
4. Update element's index in map
5. If loop completes, return false

# Solutions
### CSharp

```csharp
public class Solution { public bool ContainsNearbyDuplicate ( int [] nums , int k ) { var d = new Dictionary < int , int >(); for ( int i = 0 ; i < nums . Length ; ++ i ) { if ( d . ContainsKey ( nums [ i ]) && i - d [ nums [ i ]] <= k ) { return true ; } d [ nums [ i ]] = i ; } return false ; } }
```

### Java

```java
class Solution {
public
  boolean containsNearbyDuplicate(int[] nums, int k) {
    Map<Integer, Integer> d = new HashMap<>();
    for (int i = 0; i < nums.length; ++i) {
      if (i - d.getOrDefault(nums[i], -1000000) <= k) {
        return true;
      }
      d.put(nums[i], i);
    }
    return false;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @param {number} k * @return {boolean} */ var containsNearbyDuplicate =
  function (nums, k) {
    const d = 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;
  };

```

### CPP

```cpp
class Solution {
public:
  bool containsNearbyDuplicate(vector<int> &nums, int k) {
    unordered_map<int, int> d;
    for (int i = 0; i < nums.size(); ++i) {
      if (d.count(nums[i]) && i - d[nums[i]] <= k) {
        return true;
      }
      d[nums[i]] = i;
    }
    return false;
  }
};

```

### Python

```python
class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool: mp = {} for i, v in enumerate(nums): if v in mp and i - mp[v] <= k: return True mp[v] = i return False

```