Solution Explanation: Contains Duplicate II

The problem asks whether there exist two distinct indices i and j in the input array nums such that nums[i] == nums[j] and abs(i - j) <= k. In simpler terms: are there two identical numbers within a distance of k indices from each other?

Approach: Hash Table (Sliding Window Variation)

The most efficient approach uses a hash table (or dictionary in Python) to store the elements and their most recent indices. This approach leverages the properties of a hash table for fast lookups (O(1) on average). It's a variation of the sliding window technique, although the window size isn't fixed but implicitly defined by k.

Algorithm:

1. Initialization: Create an empty hash table d.
2. Iteration: Iterate through the nums array using a for loop.
3. Lookup: For each element nums[i]:
   • Check if the element nums[i] exists as a key in d.
   • If it exists, calculate the difference between the current index i and the index stored in d (the previous index of the same element).
   • If this difference is less than or equal to k, it means we found two identical numbers within the distance k. Return true.
4. Update: If the element is not in d or the difference is greater than k, add (or update) the element and its current index i into d.
5. Return False: If the loop completes without finding any such pair, return false.

Time and Space Complexity Analysis

• Time Complexity: O(n), where n is the length of the input array. We iterate through the array once. Hash table lookups and insertions are on average O(1).
• Space Complexity: O(min(n, k)). In the worst case (all numbers are unique), the hash table could store up to n elements. However, if k is much smaller than n, the space used will be closer to O(k) because only elements within the window of size k need to be stored.

Code Implementation (Python)

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        d = {}  # Hash table to store elements and their indices
        for i, x in enumerate(nums):
            if x in d and i - d[x] <= k:  # Check if element exists and distance <= k
                return True
            d[x] = i  # Update index for the element
        return False

The other language implementations follow the same logic, differing only in syntax and specific data structures used (e.g., HashMap in Java, unordered_map in C++, Map in TypeScript/JavaScript). The core algorithm remains consistent across all languages.