💬 Discord
Sign In
NeetCode #219LC-219EasySliding WindowNC 250
← Back to All Problems

#219 · #219 · Contains Duplicate II(存在重复元素 II)

📌 Problem Statement & Constraints

Given an integer array nums and an integer k, return true if there are two distinct indices i < j such that nums[i] == nums[j] and j - i <= k. Constraints: 1 <= nums.length <= 10^5, -10^9 <= nums[i] <= 10^9, 0 <= k <= 10^5.

💡 Core Algorithmic Approaches

  1. Maintain a sliding window of at most k distinct indices and a set of the values inside it.
  2. If the entering value is already in the set, a duplicate within distance k exists.
  3. Otherwise add it and evict the value that has just fallen out of the window.
  4. The set never needs more than k entries, so the whole scan is O(n).

💻 Benchmark Python3 Implementation

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        window = set()
        for i, x in enumerate(nums):
            if x in window:            # duplicate within distance k
                return True
            window.add(x)
            if len(window) > k:        # evict the element that left the window
                window.discard(nums[i - k])
        return False

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass with O(1) average set operations.
💾 Space Complexity
O(k) for the window.

⚠️ Interview Pitfalls & Follow-ups

  • Using len(window) > k before adding: the eviction must happen after the insertion, so the window size momentarily reaches k + 1.
  • Evicting nums[i - k - 1]: the element leaving the window when the size exceeds k is nums[i - k].
  • Storing a dict of last indices instead of a set: it works, but the set is sufficient and simpler.
  • Returning True for equal values that are farther apart than k: the distance constraint must be enforced by the window size.