Saltar al contenido principal

Contains Duplicate II

This question is asked by Google. Given an array, nums, and an integer k, return whether or not two unique indices exist such that nums[i] = nums[j] and the two indices i and j are at most k elements apart.

Example(s)​

Example 1:

Input: nums = [1, 2, 1], k = 1
Output: false
Explanation:
- nums[0] = 1, nums[2] = 1 (same value)
- Distance: |2 - 0| = 2
- Since 2 > k (1), they are NOT within k distance
- Return false

Example 2:

Input: nums = [2, 3, 2], k = 2
Output: true
Explanation:
- nums[0] = 2, nums[2] = 2 (same value)
- Distance: |2 - 0| = 2
- Since 2 <= k (2), they are within k distance
- Return true

Example 3:

Input: nums = [1, 0, 1, 1], k = 1
Output: true
Explanation:
- nums[2] = 1, nums[3] = 1 (same value)
- Distance: |3 - 2| = 1
- Since 1 <= k (1), they are within k distance
- Return true

Solution​

The solution uses a sliding window with hash map:

  1. Sliding window: Maintain a window of the last k elements
  2. Hash map: Track the most recent index of each value
  3. Check distance: If we see a duplicate, check if it's within k distance
  4. Update map: Keep track of the latest index for each value

JavaScript Solution - Hash Map

/**
* Check if duplicate exists within k distance
* @param {number[]} nums - Input array
* @param {number} k - Maximum distance allowed
* @return {boolean} - True if duplicate within k distance
*/
function containsNearbyDuplicate(nums, k) {
const indexMap = new Map();

for (let i = 0; i < nums.length; i++) {
  const num = nums[i];
  
  // Check if we've seen this number before
  if (indexMap.has(num)) {
    const lastIndex = indexMap.get(num);
    // Check if distance is within k
    if (i - lastIndex <= k) {
      return true;
    }
  }
  
  // Update the most recent index for this number
  indexMap.set(num, i);
}

return false;
}

// Test cases
console.log('Example 1:', containsNearbyDuplicate([1, 2, 1], 1)); 
// false

console.log('Example 2:', containsNearbyDuplicate([2, 3, 2], 2)); 
// true

console.log('Example 3:', containsNearbyDuplicate([1, 0, 1, 1], 1)); 
// true

console.log('Test 4:', containsNearbyDuplicate([1, 2, 3, 1], 3)); 
// true
Output:
Click "Run Code" to execute the code and see the results.

Alternative Solution (Sliding Window with Set)​

Here's a version using a set to maintain a sliding window:

/**
 * Sliding window with set approach
 */
function containsNearbyDuplicateSet(nums, k) {
  const window = new Set();
  
  for (let i = 0; i < nums.length; i++) {
    // Remove element that's too far away (outside k distance)
    if (i > k) {
      window.delete(nums[i - k - 1]);
    }
    
    // If current element is in window, we found a duplicate within k
    if (window.has(nums[i])) {
      return true;
    }
    
    // Add current element to window
    window.add(nums[i]);
  }
  
  return false;
}

Test the Alternative Solution (Sliding Window with Set)​

JavaScript Alternative - Sliding Window with Set

/**
* Sliding window with set approach
*/
function containsNearbyDuplicateSet(nums, k) {
const window = new Set();

for (let i = 0; i < nums.length; i++) {
  // Remove element that's too far away (outside k distance)
  if (i > k) {
    window.delete(nums[i - k - 1]);
  }
  
  // If current element is in window, we found a duplicate within k
  if (window.has(nums[i])) {
    return true;
  }
  
  // Add current element to window
  window.add(nums[i]);
}

return false;
}

// Test cases
console.log('Example 1:', containsNearbyDuplicateSet([1, 2, 1], 1)); // false
console.log('Example 2:', containsNearbyDuplicateSet([2, 3, 2], 2)); // true
console.log('Example 3:', containsNearbyDuplicateSet([1, 0, 1, 1], 1)); // true
Output:
Click "Run Code" to execute the code and see the results.

Complexity​

  • Time Complexity: O(n) - Where n is the length of the array. We visit each element once.
  • Space Complexity: O(min(n, k)) - The hash map/set stores at most k+1 elements (sliding window size).

Approach​

The solution uses a hash map to track indices:

  1. Track last index:

    • For each value, store its most recent index
    • When we see a duplicate, check the distance

  2. Check distance:

    • If nums[i] == nums[j] and |i - j| <= k, return true
    • We only need to check the most recent occurrence (closest to current)

  3. Update map:

    • Always update the index for the current value
    • This ensures we always check against the closest duplicate

Key Insights​

  • Hash map: Efficiently track the last index of each value
  • Check closest: Only need to check the most recent occurrence
  • Distance check: i - lastIndex <= k means within k distance
  • O(n) time: Single pass through the array
  • O(min(n,k)) space: Sliding window size is bounded by k

Step-by-Step Example​

Let's trace through Example 1: nums = [1, 2, 1], k = 1

indexMap = {}

i = 0: num = 1
  indexMap.has(1)? No
  indexMap.set(1, 0) → {1: 0}

i = 1: num = 2
  indexMap.has(2)? No
  indexMap.set(2, 1) → {1: 0, 2: 1}

i = 2: num = 1
  indexMap.has(1)? Yes
  lastIndex = 0
  distance = 2 - 0 = 2
  2 <= k (1)? No ✗
  indexMap.set(1, 2) → {1: 2, 2: 1}

Result: false (distance 2 > k=1)

Visual Representation​

Example 1: nums = [1, 2, 1], k = 1

Indices:  0  1  2
Values:  [1, 2, 1]
          ↑     ↑
        Same value, distance = 2

Distance = |2 - 0| = 2
k = 1
2 > 1 → false

Example 2: nums = [2, 3, 2], k = 2

Indices:  0  1  2
Values:  [2, 3, 2]
          ↑     ↑
        Same value, distance = 2

Distance = |2 - 0| = 2
k = 2
2 <= 2 → true

Example 3: nums = [1, 0, 1, 1], k = 1

Indices:  0  1  2  3
Values:  [1, 0, 1, 1]
          ↑     ↑  ↑
        Same values

Check (2, 3): distance = |3 - 2| = 1
1 <= 1 → true

Edge Cases​

  • k = 0: Only adjacent duplicates count
  • k >= n: All duplicates within array are valid
  • No duplicates: Return false
  • All same values: Return true if k >= 1
  • Single element: Return false (need two indices)
  • k = 1: Only consecutive duplicates count

Important Notes​

  • Unique indices: i and j must be different
  • At most k apart: Distance <= k (inclusive)
  • Most recent index: Only need to check closest duplicate
  • Update always: Always update index even if distance > k
  • O(n) time: Single pass is optimal

Why Track Most Recent Index​

Key insight: If we see a value at index i, and we've seen it before at index j:

  • If |i - j| > k, then any earlier occurrence is even farther
  • So we only need to check the most recent occurrence
  • This allows us to update the index and continue
  • Contains Duplicate: Check if any duplicates exist
  • Contains Duplicate III: Check duplicates within k distance and value difference
  • Longest Substring Without Repeating Characters: Different sliding window
  • Two Sum: Different problem

Takeaways​

  • Hash map efficiently tracks last index of each value
  • Check closest duplicate only (most recent occurrence)
  • O(n) time with single pass
  • O(min(n,k)) space for the hash map
  • Distance check is simple: |i - j| <= k