LeetCode 219: Contains Duplicate II Solution in Python Explained

Problem Statement

In LeetCode 219: Contains Duplicate II, you’re given:

• nums: An array of integers.
• k: An integer representing the maximum allowed distance between duplicates.
• Your task is to return true if there exists at least one pair of identical numbers whose indices differ by at most k, false otherwise.

This extends LeetCode 217: Contains Duplicate by adding a proximity constraint, differing from skyline computation in LeetCode 218: The Skyline Problem.

Constraints

• 1 ≤ nums.length ≤ 10⁵.
• -10⁹ ≤ nums[i] ≤ 10⁹.
• 0 ≤ k ≤ 10⁵.

Examples

Let’s see some cases:

Copy codeInput: nums = [1,2,3,1], k = 3
Output: true
Explanation: 1 at index 0 and 1 at index 3, distance = 3 ≤ k.

Copy codeInput: nums = [1,0,1,1], k = 1
Output: true
Explanation: 1 at index 2 and 1 at index 3, distance = 1 ≤ k.

Copy codeInput: nums = [1,2,3,1,2,3], k = 2
Output: false
Explanation: Duplicates (1, 2, 3) exist, but distances (3, 3, 3) exceed k=2.

These examples show we’re checking for duplicates within a window of size k.

Understanding the Problem

How do we solve LeetCode 219: Contains Duplicate II in Python? For nums = [1,2,3,1], k = 3, the two 1s are 3 indices apart (0 to 3), which is ≤ 3, so we return true. A naive approach might check every pair (O(n²)), but we can optimize with a window. This isn’t a combinatorial problem like LeetCode 216: Combination Sum III; it’s about efficiently tracking duplicates within a range. We’ll use: 1. Sliding Window with Hash Map: O(n) time, O(k) space—our best solution. 2. Brute Force with Nested Loops: O(n * min(n, k)) time, O(1) space—an alternative.

Let’s dive into the best solution.

Best Solution: Sliding Window with Hash Map Approach

Explanation

The Sliding Window with Hash Map approach maintains a window of size k:

• Use a dictionary to store numbers and their most recent indices.
• Slide through the array:
• If a number is in the map and its previous index is within k distance, return true.
• Update the map with the current index, removing elements outside the window.
• If no duplicates are found, return false.

This runs in O(n) time (single pass) and O(k) space (map stores at most k+1 elements), making it efficient and elegant—our best solution.

For [1,2,3,1], k=3, it detects the second 1 within the window.

Step-by-Step Example

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

Goal: Return true.

• Step 1: Initialize.
• window = {{ (empty dict), k = 3.
• Step 2: Iterate through nums.
• i=0, num=1: Not in window, add window={1:0{.
• i=1, num=2: Not in window, add window={1:0, 2:1{.
• i=2, num=3: Not in window, add window={1:0, 2:1, 3:2{.
• i=3, num=1: In window, check distance: 3 - 0 = 3 ≤ 3, return true.
• Output: true.

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

Goal: Return false.

• Step 1: window = {{.
• Step 2:
• i=0, num=1: window={1:0{.
• i=1, num=2: window={1:0, 2:1{.
• i=2, num=3: window={1:0, 2:1, 3:2{.
• i=3, num=4: window={2:1, 3:2, 4:3{ (remove 1, i-2=1 > 0).
• Step 3: No duplicates within k, return false.
• Output: false.

How the Code Works (Sliding Window with Hash Map) – Detailed Line-by-Line Explanation

Here’s the Python code with a detailed breakdown:

Copy codedef containsNearbyDuplicate(nums: list[int], k: int) -> bool:
    # Line 1: Initialize hash map
    window = {{
    # Dictionary for number:index (e.g., {{)

    # Line 2: Iterate with sliding window
    for i, num in enumerate(nums):
        # Process each element (e.g., i=0, num=1)
        if num in window and abs(i - window[num]) <= k:
            # Check if duplicate within k (e.g., 3-0 ≤ 3)
            return True
            # Duplicate found (e.g., true)

        window[num] = i
        # Update index (e.g., window={1:0{)

        # Line 3: Maintain window size
        if i >= k:
            # Window exceeds k (e.g., i=3, k=3)
            del window[nums[i - k]]
            # Remove old element (e.g., remove nums[0])

    # Line 4: No duplicates within k
    return False
    # All unique within k (e.g., false)

This solution efficiently tracks duplicates within the window.

Alternative: Brute Force with Nested Loops Approach

Explanation

The Brute Force with Nested Loops approach checks pairs within k:

• For each element, look ahead up to k positions.
• If a match is found, return true.
• If no matches are found, return false.

It’s O(n * min(n, k)) time (nested loops) and O(1) space, simple but less efficient.

Step-by-Step Example

For [1,2,3,1], k=3:

• i=0, num=1: Check [2,3,1], finds 1 at i=3, distance=3, true.
• Output: true.

For [1,2,3,4], k=2:

• i=0: [2,3], no 1.
• i=1: [3,4], no 2.
• i=2: [4], no 3.
• i=3: [], no 4.
• Output: false.

How the Code Works (Brute Force)

Copy codedef containsNearbyDuplicateBrute(nums: list[int], k: int) -> bool:
    for i in range(len(nums)):
        for j in range(i + 1, min(len(nums), i + k + 1)):
            if nums[i] == nums[j]:
                return True
    return False

Complexity

• Sliding Window with Hash Map:
• Time: O(n) – single pass with O(1) map operations.
• Space: O(k) – map stores at most k+1 elements.
• Brute Force with Nested Loops:
• Time: O(n * min(n, k)) – check up to k elements per index.
• Space: O(1) – no extra space.

Efficiency Notes

Sliding Window with Hash Map is our best solution with O(n) time and reasonable space usage, perfect for this problem. Brute Force is slower but uses minimal memory, viable for small inputs.

Key Insights

• Window: Limits search scope.
• Hash Map: Fast lookups.
• Distance: Core constraint.

Additional Example

For [1,2,1,3,1], k=2:

• Hash Map: 1 at 0 and 2, distance=2, true.
• Brute: Same result, checks pairs.

Edge Cases

• k=0: false (no distance allowed).
• Single element: false.
• k ≥ n: Like [LeetCode 217](/leetcode/217/contains-duplicate).

Both handle these well.

Final Thoughts

LeetCode 219: Contains Duplicate II in Python is a great step up from basic duplicate checking. Sliding Window with Hash Map offers speed and elegance, while Brute Force provides a simple baseline. Want more? Try LeetCode 217: Contains Duplicate or LeetCode 220: Contains Duplicate III. Test your skills—Solve LeetCode 219 on LeetCode with [1,2,3,1], k=3 (expecting true)—find those nearby duplicates today!