Contains Duplicate Ii - Leetcode Solution

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.

1