Last updated on August 5th, 2024 at 01:01 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
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.