LeetCode 220: Contains Duplicate III Solution in Python Explained

Problem Statement

In LeetCode 220: Contains Duplicate III, you’re given:

• nums: An array of integers.
• k: An integer representing the maximum index distance.
• t: An integer representing the maximum value difference.
• Your task is to return true if there exist two indices i and j such that abs(i - j) ≤ k and abs(nums[i] - nums[j]) ≤ t, false otherwise.

This builds on LeetCode 219: Contains Duplicate II by adding a value tolerance, differing from skyline computation in LeetCode 218: The Skyline Problem.

Constraints

• 0 ≤ nums.length ≤ 2 * 10⁴.
• -2³¹ ≤ nums[i] ≤ 2³¹ - 1.
• 0 ≤ k ≤ 10⁴.
• 0 ≤ t ≤ 2³¹ - 1.

Examples

Let’s see some cases:

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

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

Copy codeInput: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false
Explanation: Duplicates exist, but distances (3) > k=2, and differences (4) > t=3.

These examples show we’re checking for near-duplicates within constraints.

Understanding the Problem

How do we solve LeetCode 220: Contains Duplicate III in Python? For nums = [1,2,3,1], k = 3, t = 0, the two 1s are 3 indices apart (≤ 3) and differ by 0 (≤ 0), so true. A brute-force check of all pairs is O(n²), but a sliding window optimizes this. This isn’t a combination problem like LeetCode 216: Combination Sum III; it’s about efficiently comparing values within a range. We’ll use: 1. Sliding Window with Buckets: O(n) time, O(k) space—our best solution. 2. Sliding Window with BST: O(n log k) time, O(k) space—an alternative.

Let’s dive into the best solution.

Best Solution: Sliding Window with Buckets Approach

Explanation

The Sliding Window with Buckets approach uses a hash map with bucketing:

• Divide numbers into buckets of size t+1 (to ensure numbers within t are in the same or adjacent buckets).
• Maintain a window of size k:
• For each number, check its bucket and adjacent buckets for a value within t.
• Add the number to its bucket, remove elements outside the window.
• Return true if a near-duplicate is found, false otherwise.

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

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

Step-by-Step Example

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

Goal: Return true.

• Step 1: Initialize.
• buckets = {{, bucket_size = t + 1 = 1.
• Step 2: Iterate with window.
• i=0, num=1: Bucket = 1//1 = 1, buckets={1:1{.
• i=1, num=2: Bucket = 2//1 = 2, buckets={1:1, 2:2{.
• i=2, num=3: Bucket = 3//1 = 3, buckets={1:1, 2:2, 3:3{.
• i=3, num=1: Bucket = 1//1 = 1, check:
• Same bucket: buckets[1]=1, diff = 1-1=0 ≤ 0, true.
• Output: true.

Example 2: nums = [1,5,9,1,5,9], k = 2, t = 3

Goal: Return false.

• Step 1: buckets = {{, bucket_size = 4.
• Step 2:
• i=0, num=1: Bucket = 1//4=0, buckets={0:1{.
• i=1, num=5: Bucket = 5//4=1, buckets={0:1, 1:5{.
• i=2, num=9: Bucket = 9//4=2, buckets={0:1, 1:5, 2:9{.
• i=3, num=1: Remove i-2=1, buckets={1:5, 2:9{, bucket=0, diff=4 > 3, add buckets={0:1, 1:5, 2:9{.
• i=4, num=5: Remove i-2=2, bucket=1, diff=0 ≤ 3, but distance=3 > 2, buckets={0:1, 1:5{.
• i=5, num=9: Remove i-2=3, bucket=2, diff=4 > 3, buckets={1:5, 2:9{.
• Output: false.

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

Here’s the Python code with a detailed breakdown:

Copy codedef containsNearbyAlmostDuplicate(nums: list[int], k: int, t: int) -> bool:
    # Line 1: Handle edge cases and initialize
    if k < 0 or t < 0:
        # Invalid input (e.g., k=-1)
        return False
        # No duplicates possible
    buckets = {{
    # Bucket map (e.g., {{)
    bucket_size = t + 1
    # Bucket width (e.g., 1 for t=0)

    # Line 2: Iterate with sliding window
    for i, num in enumerate(nums):
        # Process each element (e.g., i=0, num=1)
        bucket = num // bucket_size
        # Compute bucket (e.g., 1//1=1)

        # Line 3: Check current and adjacent buckets
        if bucket in buckets:
            # Same bucket (e.g., 1 in {1:1{)
            return True
            # Diff ≤ t (e.g., true)
        if bucket - 1 in buckets and abs(num - buckets[bucket - 1]) <= t:
            # Previous bucket (e.g., diff=1-0 ≤ 2)
            return True
        if bucket + 1 in buckets and abs(num - buckets[bucket + 1]) <= t:
            # Next bucket (e.g., diff=2-3 ≤ 2)
            return True

        # Line 4: Add to bucket and maintain window
        buckets[bucket] = num
        # Store number (e.g., {1:1{)
        if i >= k:
            # Window exceeds k (e.g., i=3, k=3)
            del buckets[nums[i - k] // bucket_size]
            # Remove old bucket (e.g., del 0)

    # Line 5: No near-duplicates found
    return False
    # No matches (e.g., false)

This solution cleverly uses buckets to approximate value differences.

Alternative: Sliding Window with BST Approach

Explanation

The Sliding Window with BST approach uses a balanced BST:

• Maintain a BST (e.g., TreeSet or SortedList) of the last k elements.
• For each number, find the closest values (successor and predecessor).
• Check if the difference is ≤ t.
• Add the number, remove the oldest if window exceeds k.

It’s O(n log k) time (BST operations) and O(k) space, precise but slower.

Step-by-Step Example

For [1,5,9,1], k=2, t=3:

• i=0, num=1: BST=[1].
• i=1, num=5: BST=[1,5], diff=4 > 3.
• i=2, num=9: BST=[5,9], diff=4 > 3.
• i=3, num=1: BST=[9,1], diff=8 > 3, no match within k.
• Output: false.

How the Code Works (BST)

Copy codefrom sortedcontainers import SortedList

def containsNearbyAlmostDuplicateBST(nums: list[int], k: int, t: int) -> bool:
    if k < 0 or t < 0:
        return False

    window = SortedList()
    for i, num in enumerate(nums):
        if i > k:
            window.remove(nums[i - k - 1])

        pos = window.bisect_left(num)
        if pos > 0 and abs(num - window[pos - 1]) <= t:
            return True
        if pos < len(window) and abs(num - window[pos]) <= t:
            return True

        window.add(num)

    return False

Complexity

• Sliding Window with Buckets:
• Time: O(n) – single pass with O(1) bucket checks.
• Space: O(k) – bucket map size.
• Sliding Window with BST:
• Time: O(n log k) – BST operations per element.
• Space: O(k) – BST size.

Efficiency Notes

Sliding Window with Buckets is our best solution with O(n) time and practical space usage, leveraging bucketing for speed. BST is more precise but slower due to logarithmic operations.

Key Insights

• Buckets: Approximate differences.
• Window: Limits distance.
• Tolerance: Adds flexibility.

Additional Example

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

• Buckets: No diffs ≤ 2 within k=2, false.
• BST: Same result.

Edge Cases

• t=0: Like [LeetCode 219](/leetcode/219/contains-duplicate-ii).
• k=0: Only same index, false.
• Single element: false.

Both handle these well.

Final Thoughts

LeetCode 220: Contains Duplicate III in Python is a fascinating extension of duplicate detection. Sliding Window with Buckets shines with efficiency, while BST offers precision. Want more? Try LeetCode 219: Contains Duplicate II or LeetCode 1: Two Sum. Test your skills—Solve LeetCode 220 on LeetCode with [1,2,3,1], k=3, t=0 (expecting true)—spot those near-duplicates today!