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.
1var containsNearbyDuplicate = function(nums, k) {
2 const map = new Map();
3 for (let i = 0; i < nums.length; i++) {
4 if (map.has(nums[i]) && (i - map.get(nums[i]) <= k)) {
5 return true;
6 }
7 map.set(nums[i], i);
8 }
9 return false;
10};The JavaScript function uses a Map object to store indices of the elements. As the function traverses the input array, it assesses whether the condition for proximity is satisfied before setting a new index for each number.
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.