LeetCode: Contains Duplicate II

Problem:

https://leetcode.com/problems/contains-duplicate-ii/

Code:

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        # window = k
        seen_in_window = set()
        for i in range(len(nums)):
            if i>k:
                seen_in_window.discard(nums[i-k-1])
            if nums[i] in seen_in_window:
                return True
            else:
                seen_in_window.add(nums[i])
        return False

Key Points:

Problem in Simple Words

You are given an array of numbers and an integer k. You must check whether there are two equal numbers such that:

• Their indices differ by at most k

In short:

Same value + close enough positions → return True

Example:

• nums = [1,2,3,1], k = 3 → True

• nums = [1,0,1,1], k = 1 → True

• nums = [1,2,3,1,2,3], k = 2 → False

---

Core Idea (Sliding Window + Set)

We only care about duplicates within distance k. So we maintain a sliding window of size k using a set.

The set always stores:

• the last k elements we have seen

---

How the Algorithm Works

• Traverse the array from left to right

• For each index i:

  1. If the window size exceeds k:

     • Remove the element that just moved out of the window
       (nums[i - k - 1])

  2. Check if the current number already exists in the window:

     • If yes → duplicate within range → return True

     • If no → add it to the window

If we finish the loop without finding duplicates → return False

---

Why Removing nums[i - k - 1] Is Important

• It keeps the window size limited to k

• Ensures we only compare elements whose index difference ≤ k

• Prevents false positives from far-away duplicates

---

Why a Set Is Perfect Here

• Fast lookup: O(1)

• No duplicate storage

• Automatically tracks what’s inside the current window

---

Why This Works

At any index i, the set contains exactly the elements from: indices: [i - k, i - 1]

So if nums[i] is already in the set:

• There exists some j where:

  • nums[i] == nums[j]

  • |i - j| ≤ k

Which is exactly the condition asked.

---

Edge Cases Covered

• k = 0 → window always empty → always False

• Array with no duplicates → False

• Duplicate values but too far apart → correctly ignored

---

Complexity

• Time: O(n)

• Space: O(k)

---

Key Insight to Remember

Whenever a problem says:

“same value within a distance constraint”

👉 Think sliding window + set, not brute force.