Sponsored
Sponsored
This approach utilizes a hash map (dictionary) to maintain a mapping between array elements and their indices. As we iterate through the array, we check if the current element already exists in the hash map. If it does, we calculate the difference between the current index and the stored index and check if it is less than or equal to k. If this condition is met, we return true. Otherwise, we update the hash map with the current index for the element.
Time Complexity: O(n), where n is the number of elements in the array, since each insert/find operation is linear.
Space Complexity: O(min(n, k)), where n is the number of elements in the array, because we store at most k elements in the map at any time.
1import java.util.HashMap;
2
3public class Solution {
4 public boolean containsNearbyDuplicate(int[] nums, int k) {
5 HashMap<Integer, Integer> map = new HashMap<>();
6 for (int i = 0; i < nums.length; i++) {
7 if (map.containsKey(nums[i]) && i - map.get(nums[i]) <= k) {
8 return true;
9 }
10 map.put(nums[i], i);
11 }
12 return false;
13 }
14}The Java implementation employs a HashMap to keep track of indices of the array elements. As we traverse through the array, we consistently check the gap between the current index and the previously stored index of the same element.
This method employs a sliding window (of length k) to automatically invalidate indices of prior numbers as the window advances through the array. The structure operates similarly to a hash set within the k-restricted scope, resulting in more direct checks and validations during index alterations.
Time Complexity: O(n*k), as each number is recalculated through prior windows.
Space Complexity: O(k), correlating with the contiguous window used.
1This sample renders Python's set, implementing an efficient sliding window. Post-exit, window size is maintained at k or below via element removal, allowing examination of relatively fresh entries, revalidating whether number exists therein.