# Contains Duplicate II LeetCode Solution

Last updated on July 15th, 2024 at 01:47 am

Here, We see Contains Duplicate II LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc., with different approaches.

# List of all LeetCode Solution

Topics

Array, Hash Table

Companies

Airbnb

Level of Question

Easy

## Problem Statement

Given an integer array nums and an integer k, return true if there are two distinct indices 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```

## 1. Contains Duplicate II Leetcode Solution C++

```class Solution {
public:
bool containsNearbyDuplicate(vector&lt;int&gt;&amp; nums, int k)
{
unordered_set&lt;int&gt; s;

if (k &lt;= 0) return false;
if (k &gt;= nums.size()) k = nums.size() - 1;

for (int i = 0; i &lt; nums.size(); i++)
{
if (i &gt; k) s.erase(nums[i - k - 1]);
if (s.find(nums[i]) != s.end()) return true;
s.insert(nums[i]);
}

return false;
}
};```

#### 1.1 Explanation

1. Initialization: An unordered_set is used to track the elements within the window of size k.
2. Edge Cases: If k is non-positive, the function returns false immediately. If k is greater than or equal to the size of the array, it is adjusted.
3. Sliding Window: The loop iterates over the array, maintaining a sliding window of size k.
• Removing Out-of-Range Elements: If the current index i exceeds k , the element at i – k – 1 is removed from the set.
• Checking Duplicates: If the current element is found in the set, a duplicate within the range k is detected, and the function returns true.
• Inserting Elements: The current element is added to the set.

#### 1.2 Time Complexity

• Best Case: O(n) for iterating through the array.
• Average and Worst Case: O(n) due to hash set operations.

#### 1.3 Space Complexity

• Best Case: O(k) for storing up to k elements in the set.
• Average and Worst Case: O(k) due to the size of the set.

## 2. Contains Duplicate II Leetcode Solution Java

```class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set&lt;Integer&gt; set = new HashSet&lt;Integer&gt;();
for(int i = 0; i &lt; nums.length; i++){
if(i &gt; k) set.remove(nums[i-k-1]);
}
return false;
}
}```

#### 2.1 Explanation

1. Initialization: A HashSet is used to track the elements within the window of size k.
2. Sliding Window: The loop iterates over the array, maintaining a sliding window of size k.
• Removing Out-of-Range Elements: If the current index i exceeds k , the element at i – k – 1 is removed from the set.
• Checking Duplicates: The add method returns false if the element is already present in the set, indicating a duplicate.
• Inserting Elements: The current element is added to the set.

#### 2.2 Time Complexity

• Best Case: O(n) for iterating through the array.
• Average and Worst Case: O(n) due to hash set operations.

#### 2.3 Space Complexity

• Best Case: O(k) for storing up to k elements in the set.
• Average and Worst Case: O(k) due to the size of the set.

## 3. Contains Duplicate II Leetcode Solution JavaScript

```var containsNearbyDuplicate = function(nums, k) {
const hasmap = new Map();
for (let idx = 0; idx &lt; nums.length; idx++) {
if (idx - hasmap.get(nums[idx]) &lt;= k) {
return true;
}
hasmap.set(nums[idx], idx);
}
return false;
};```

#### 3.1 Explanation

1. Initialization: A Map is used to track the indices of elements.
2. Sliding Window: The loop iterates over the array.
• Checking Duplicates: If the difference between the current index and the stored index of the current element is within k, a duplicate is detected.
• Updating Indices: The current element’s index is updated in the map.

#### 3.2 Time Complexity

• Best Case: O(n) for iterating through the array.
• Average and Worst Case: O(n) due to hash set operations.

#### 3.3 Space Complexity

• Best Case: O(k) for storing up to k elements in the set.
• Average and Worst Case: O(k) due to the size of the set.

## 4. Contains Duplicate II Leetcode Solution Python

```class Solution:
def containsNearbyDuplicate(self, nums, k):
dic = {}
for i, v in enumerate(nums):
if v in dic and i - dic[v] &lt;= k:
return True
dic[v] = i
return False```

#### 4.1 Explanation

1. Initialization: A dictionary is used to track the indices of elements.
2. Sliding Window: The loop iterates over the array.
• Checking Duplicates: If the current element is already in the dictionary and the difference between the current index and the stored index is within k, a duplicate is detected.
• Updating Indices: The current element’s index is updated in the dictionary.

#### 4.2 Time Complexity

• Best Case: O(n) for iterating through the array.
• Average and Worst Case: O(n) due to dictionary operations.

#### 4.3 Space Complexity

• Best Case: O(k) for storing up to k elements in the dictionary.
• Average and Worst Case: O(k) due to the size of the dictionary.
Scroll to Top