219. Contains Duplicate II

Intuition

To determine if there are two distinct indices i and j in the array nums such that nums[i] == nums[j] and the absolute difference between i and j is less than or equal to k, we can utilize a hash map (or dictionary) to keep track of the indices of the elements we encounter as we iterate through the array. This allows us to efficiently check if we have seen the same element within the desired range.

Approach

1. Initialize a dictionary: We will use a dictionary to store each element in the array and its corresponding index as we iterate through the array.
2. Iterate through the array: For each element in the array: - Check if the element is already in the dictionary. - If it is, calculate the difference between the current index and the index stored in the dictionary. - If the difference is less than or equal to k, return true. - Update the dictionary with the current element and its index.
3. Return false: If we complete the iteration without finding any valid pairs, return false.

Complexity

Time Complexity:

O(n), where n is the number of elements in the array. We traverse the array once, and each dictionary operation (insertion and lookup) is O(1) on average.

Space Complexity:

O(n) in the worst case, where n is the number of elements in the array. In the worst case, all elements are unique and stored in the dictionary.

Code

C++

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

Python

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        num_map = {}
        for i in range(len(nums)):
            if nums[i] in num_map:
                if (i - num_map[nums[i]]) <= k:
                    return True
            num_map[nums[i]] = i
        return False

Java

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                if ((i - map.get(nums[i])) <= k) {
                    return true;
                }
            }
            map.put(nums[i], i);
        }
        return false;
    }
}

JavaScript

var containsNearbyDuplicate = function (nums, k) {
let map = new Map()
    for (let i = 0; i < nums.length; i++) {
        if(map.has(nums[i])){
            if(( i - map.get(nums[i]) ) <= k)return true
        }map.set(nums[i] , i)
    }return false
};