Solution For Contains Duplicate Ii

The problem statement of Contains Duplicate II is as follows:

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.

To solve this problem, we need to keep track of the indices of each number in the array. We also need to keep track of the last index that each number appeared at. If we encounter a number that has already appeared before and the difference between its current index and its last index is less than or equal to k, then we return true. Otherwise, we update the last index of the number.

Here is the detailed solution:

1. Create a hash table to store the indices of the numbers in the array.
2. Traverse the array from left to right.
3. Check if the current number is already in the hash table.
4. If the number is already in the hash table, then check the difference between its current index and its last index.
5. If the difference is less than or equal to k, then return true.
6. Otherwise, update the last index of the number in the hash table.
7. If the number is not in the hash table, then add it to the hash table with its index as the value.
8. If we have reached the end of the array without finding any duplicates, then return false.

Here is the Python code for the solution:

def containsNearbyDuplicate(nums, k):
num_dict = {}
for i in range(len(nums)):
if nums[i] in num_dict and i – num_dict[nums[i]] <= k:
return True
else:
num_dict[nums[i]] = i
return False

We can test the solution on the following test cases:

Input: nums = [1,2,3,1], k = 3
Output: True
Explanation: The two indices at which the number 1 appears are 0 and 3, and the difference between them is 3, which is less than or equal to k.

Input: nums = [1,0,1,1], k = 1
Output: True
Explanation: The two indices at which the number 1 appears are 0 and 2, and the difference between them is 2, which is less than or equal to k.

Input: nums = [1,2,3,1,2,3], k = 2
Output: False
Explanation: Although the numbers 1 and 2 appear more than once in the array, their difference in indices is always greater than k. Hence there are no duplicates with absolute difference less than or equal to k.

Step by Step Implementation For Contains Duplicate Ii

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        // create a set to store unique elements
        Set set = new HashSet<>();
        
        // iterate through the array
        for (int i = 0; i < nums.length; i++) {
            // if the set already contains the current element,
            // it means we have found a duplicate
            if (set.contains(nums[i])) {
                return true;
            }
            // add the current element to the set
            set.add(nums[i]);
            
            // if the set size is greater than k,
            // remove the element at the previous index
            if (set.size() > k) {
                set.remove(nums[i - k]);
            }
        }
        return false;
    }
}

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        # create a set to store unique elements 
        unique_elements = set() 
          
        # traverse the input array 
        for i in range(len(nums)): 
            # if element is already in set 
            if nums[i] in unique_elements: 
                return True
              
            # insert the element in the set 
            unique_elements.add(nums[i]) 
              
        # return false if no duplicate element is found 
        return False

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
var containsNearbyDuplicate = function(nums, k) {
    // create an empty object
    let obj = {};
    
    // loop through the array
    for (let i = 0; i < nums.length; i++) {
        // check if the current element is in the object
        if (obj[nums[i]]) {
            // if it is, check if the difference between the current index and the index of the element in the object is less than or equal to k
            if (i - obj[nums[i]] <= k) {
                // if it is, return true
                return true;
            }
        }
        // if the current element is not in the object, add it with the current index
        obj[nums[i]] = i;
    }
    // if we get through the loop and don't return true, return false
    return false;
};

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

public class Solution {
    public bool ContainsDuplicate(int[] nums, int k) {
        // create a dictionary to store the elements and their indices
        Dictionary map = new Dictionary();
        
        // loop through the array
        for (int i = 0; i < nums.Length; i++) {
            // check if the dictionary contains the current element
            if (map.ContainsKey(nums[i])) {
                // check if the difference between the current index and the stored index is less than or equal to k
                if (i - map[nums[i]] <= k) {
                    // return true if it is
                    return true;
                }
            }
            // update the dictionary with the current element and index
            map[nums[i]] = i;
        }
        // return false if no duplicate is found
        return false;
    }
}