{x}
blog image

Contains Duplicate II

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.

 

Example 1:

Input: nums = [1,2,3,1], k = 3
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1
Output: true

Example 3:

Input: nums = [1,2,3,1,2,3], k = 2
Output: false

 

Constraints:

  • 1 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • 0 <= k <= 105

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.