Contains Duplicate II LeetCode Solution

Last updated on October 10th, 2024 at 12:51 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

Contains Duplicate II LeetCode Solution

Contains Duplicate II LeetCode Solution

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]);
            if(!set.add(nums[i])) return true;
        }
        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