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.
1class Solution:
2 def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
3 index_map = {}
4 for i, number in enumerate(nums):
5 if number in index_map and i - index_map[number] <= k:
6 return True
7 index_map[number] = i
8 return FalseThe Python code relies on a dictionary to maintain a relationship between array elements and their indices. At each iteration, the method verifies if the current number already appears within the allowed distance, consequently updating the index in the dictionary.
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.
1
The Java equivalent harnesses a HashSet for activity. It replaces crafted entries continually, monitoring a maximum count equivalent to k+1, while ensuring that no two duplicated digits exist within this scope. Duplicate recognition signifies success.