Skip to main content

🟩 Contains Duplicate II (#219)

🔗 Problem Link​

📋 Problem Statement​

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.

💡 Examples​

Example 1​

Input: nums = [1,2,3,1], k = 3
Output: true
Explanation: nums[0] == nums[3] and abs(0 - 3) = 3 <= k

Example 2​

Input: nums = [1,0,1,1], k = 1
Output: true
Explanation: nums[2] == nums[3] and abs(2 - 3) = 1 <= k

Example 3​

Input: nums = [1,2,3,1,2,3], k = 2
Output: false
Explanation: No two equal elements are within distance k

🔑 Key Insights & Approach​

Core Observation: We need to check if a duplicate exists within a window of size k. This transforms the problem from "find any duplicate" to "find duplicate within k distance."

Why Sliding Window with Hash Set?

  • Distance constraint: Only care about elements within last k positions
  • Fast lookup: Hash set provides O(1) duplicate checking
  • Window maintenance: Keep only last k elements in the set

The Mental Model: Think of a sliding window of size k moving through the array. At each position, we ask: "Is the current number already in my window?" If yes, we found a duplicate within distance k.

Algorithm Steps:

  1. Iterate through array: For each element at index i
  2. Check if exists: If current number is in the set, return true
  3. Add to window: Add current number to set
  4. Maintain window size: If window exceeds size k, remove the leftmost element

Why This Works:

  • Set contains at most k elements (the sliding window)
  • If we find a duplicate in the set, it must be within last k positions
  • We remove elements that are too far away (more than k positions back)

Pattern Recognition: This is the "Sliding Window with Hash Set" pattern - when you need to track elements within a fixed distance or time window.

🐍 Solution: Python​

Approach 1: Sliding Window with Hash Set​

Time Complexity: O(n) | Space Complexity: O(min(n, k))

def containsNearbyDuplicate(nums: List[int], k: int) -> bool:
    window = set()

    for i, num in enumerate(nums):
        # Check if duplicate exists in current window
        if num in window:
            return True

        # Add current number to window
        window.add(num)

        # Maintain window size of k
        if len(window) > k:
            # Remove the leftmost element (nums[i-k])
            window.remove(nums[i - k])

    return False

Approach 2: Hash Map with Last Index​

Time Complexity: O(n) | Space Complexity: O(n)

def containsNearbyDuplicate(nums: List[int], k: int) -> bool:
    last_seen = {}  # num -> last index

    for i, num in enumerate(nums):
        # If we've seen this number before
        if num in last_seen:
            # Check if within distance k
            if i - last_seen[num] <= k:
                return True

        # Update last seen index
        last_seen[num] = i

    return False

🔵 Solution: Golang​

Approach 1: Sliding Window with Hash Set​

Time Complexity: O(n) | Space Complexity: O(min(n, k))

func containsNearbyDuplicate(nums []int, k int) bool {
    window := make(map[int]bool)

    for i, num := range nums {
        // Check if duplicate in window
        if window[num] {
            return true
        }

        // Add to window
        window[num] = true

        // Maintain window size
        if len(window) > k {
            delete(window, nums[i-k])
        }
    }

    return false
}

Approach 2: Hash Map with Last Index​

Time Complexity: O(n) | Space Complexity: O(n)

func containsNearbyDuplicate(nums []int, k int) bool {
    lastSeen := make(map[int]int)

    for i, num := range nums {
        // Check if seen before
        if lastIdx, exists := lastSeen[num]; exists {
            if i - lastIdx <= k {
                return true
            }
        }

        // Update last seen
        lastSeen[num] = i
    }

    return false
}

📚 References​