algoadvance

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.

Clarifying Questions

1. Can the array contain negative numbers or only positive integers?
   • The array can contain both negative and positive integers.
2. What is the range of values for k?
   • k can be any non-negative integer within the constraints of typical LeetCode problems, commonly up to 10^5.
3. What should we return if the nums array is empty or contains a single element?
   • If the nums array is empty or has only one element, return false since no indices i and j can satisfy the condition.
4. Is the input always valid?
   • Yes, you can assume that nums and k are always valid inputs.

Strategy

We need to track the indices of elements we have seen while traversing the array. Here’s a concise plan to achieve this:

1. Use a dictionary to store the last index of each element.
2. As we traverse the list, for each element, check if it exists in the dictionary:
   • If it exists, calculate the absolute difference between the current index and the stored index.
   • If the difference is less than or equal to k, return true.
   • Otherwise, update the dictionary with the current index of the element.
3. If we finish traversing the list without finding any such pairs, return false.

Code

def containsNearbyDuplicate(nums, k):
    index_map = {}
    
    for i, num in enumerate(nums):
        if num in index_map and i - index_map[num] <= k:
            return True
        index_map[num] = i
    
    return False

Time Complexity

• Time Complexity: O(n), where n is the number of elements in the nums array. We traverse the list once, and dictionary operations (insertion and lookup) are on average O(1).

• Space Complexity: O(min(n, k)), as the dictionary will at most store k elements due to the sliding window constraint.

This solution efficiently checks for duplicate elements within the given index distance constraint, ensuring optimal performance for large inputs.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?