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:

1
2

Input nums = [1,2,3,1], k = 3
Output: true

Example 2:

1
2

Input: nums = [1,0,1,1], k = 1
Output: true

Example 3:

1
2

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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)