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
![Contains Duplicate II LeetCode Solution](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2024/02/LeetCode-Problem-Solution.png?resize=200%2C200&ssl=1)
Contains Duplicate II LeetCode Solution
Table of Contents
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
1. Contains Duplicate II Leetcode Solution C++
class Solution { public: bool containsNearbyDuplicate(vector<int>& nums, int k) { unordered_set<int> s; if (k <= 0) return false; if (k >= nums.size()) k = nums.size() - 1; for (int i = 0; i < nums.size(); i++) { if (i > 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
- Initialization: An unordered_set is used to track the elements within the window of size k.
- 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.
- 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<Integer> set = new HashSet<Integer>(); for(int i = 0; i < nums.length; i++){ if(i > k) set.remove(nums[i-k-1]); if(!set.add(nums[i])) return true; } return false; } }
2.1 Explanation
- Initialization: A HashSet is used to track the elements within the window of size k.
- 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 < nums.length; idx++) { if (idx - hasmap.get(nums[idx]) <= k) { return true; } hasmap.set(nums[idx], idx); } return false; };
3.1 Explanation
- Initialization: A Map is used to track the indices of elements.
- 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] <= k: return True dic[v] = i return False
4.1 Explanation
- Initialization: A dictionary is used to track the indices of elements.
- 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.