Domain 1EasyCORE

Contains Duplicate II

The problem asks us to determine if there are two distinct indices `i` and `j` in an integer array `nums` such that the values at these indices are equal (`nums[i] == nums[j]`) and the absolute difference between the indices is less than or equal to a given integer `k` (`abs(i - j) <= k`). The inputs are the array `nums` and the integer `k`. The output should be a boolean value: `true` if such indices exist, otherwise `false`.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array#Hash Table

219. Contains Duplicate II

Model: qwen2.5-coder:14b
Topics: Array,Hash Table
FAANG asked: 1
Acceptance rate: 38.8%


Problem Breakdown

The problem asks us to determine if there are two distinct indices i and j in an integer array nums such that the values at these indices are equal (nums[i] == nums[j]) and the absolute difference between the indices is less than or equal to a given integer k (abs(i - j) <= k). The inputs are the array nums and the integer k. The output should be a boolean value: true if such indices exist, otherwise false.

Implicit constraints include:

  • The array can contain duplicate values.
  • The array can have negative numbers.
  • The array length is between 1 and (10^5).
  • The value of k is between 0 and (10^5).

Edge cases to consider:

  • An empty array should return false.
  • If k is 0, the only way to satisfy the condition is if there are duplicate values at the same index, which is not possible.
  • Large arrays with many duplicates.

Intuition

A brute-force approach would involve checking every pair of indices (i, j) where j > i and verifying if nums[i] == nums[j] and abs(i - j) <= k. This approach has a time complexity of (O(n^2)), which is inefficient for large arrays.

The key insight to improve this solution is to use a hash table (dictionary in Python) to keep track of the most recent index where each value was seen. By doing so, we can check in constant time if a duplicate exists within the required distance k.

Approach

  1. Initialize an empty dictionary index_map to store the last seen index of each number.
  2. Iterate through the array nums using an index i.
  3. For each element num at index i:
    • Check if num is already in index_map and if the difference between the current index i and the stored index is less than or equal to k.
      • If true, return true.
    • Update the dictionary with the current index i for the number num.
  4. If no such pair of indices is found by the end of the iteration, return false.

This approach ensures that each element is processed only once, leading to a linear time complexity.

Complexity Analysis

  • Time Complexity: (O(n)), where (n) is the length of the array nums. Each element is processed at most twice (once when added to the dictionary and once when checked).
  • Space Complexity: (O(min(n, k))). In the worst case, all elements are stored in the dictionary. However, since we only need to keep track of the last k indices for each number, the space complexity is limited by k.

Solution

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

Edge Cases Handled

  • Empty Array: The loop will not execute, and the function will return false.
  • k = 0: Since we only update the dictionary when a duplicate is found within distance k, this case is naturally handled.
  • Large Arrays with Many Duplicates: The solution efficiently handles large inputs by maintaining a limited-size dictionary.