Contains Duplicate 2 - within k distance

Problem

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.

OR

Given an array of integer, find duplicates which are within k indices away.

Examples

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

Solution

Method 1 - Using HashSet and sliding window

We can follow following steps:

1. Initialize a HashSet: To store elements within the current sliding window of size k.
2. Iterate through the array: Using a for loop to process each element.
   1. Remove out-of-range elements: If the current index i exceeds k, remove the element that is k+1 positions behind from the set to maintain the window size.
   2. Add current element to the set: Try adding the current element to the HashSet.
   3. Check for duplicates: If the element already exists in the set, return true (duplicate found within range).
3. Return false if no duplicates are found: After iterating through all elements in the array.

Code

Java

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;
 }

Complexity

• ⏰ Time complexity: O(n)
• 🧺 Space complexity: O(k)

Method 2 - Using HashMap

We can follow following steps:

1. Initialize a HashMap: To store elements and their corresponding indices.
2. Iterate through the array: Using a for loop to process each element.
   1. Check if the element is already in the map: Determine if the current element has been seen before.
   2. Check index difference: If the element is in the map, compare the current index with the stored index. If the difference is less than or equal to k, return true.
   3. Update the map: Store the current element and its index in the map.
3. Return false if no duplicates are found: After iterating through all elements in the array.

Code

Java

public boolean containsNearbyDuplicate(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    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;
}

Complexity

• ⏰ Time complexity: O(n)
• 🧺 Space complexity: O(n)