LeetCode 220: Contains Duplicate III

Problem Description

LeetCode Problem 220

You are given an integer array nums and two integers indexDiff and valueDiff.

Find a pair of indices (i, j) such that:

• i != j,
• abs(i - j) <= indexDiff.
• abs(nums[i] - nums[j]) <= valueDiff, and

Return true if such pair exists or false otherwise.

Example 1:

Input: nums = [1,2,3,1], indexDiff = 3, valueDiff = 0
Output: true
Explanation: We can choose (i, j) = (0, 3).
We satisfy the three conditions:
i != j --> 0 != 3
abs(i - j) <= indexDiff --> abs(0 - 3) <= 3
abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0

Example 2:

Input: nums = [1,5,9,1,5,9], indexDiff = 2, valueDiff = 3
Output: false
Explanation: After trying all the possible pairs (i, j), we cannot satisfy the three conditions, so we return false.

Constraints:

• 2 <= nums.length <= 105
• -109 <= nums[i] <= 109
• 1 <= indexDiff <= nums.length
• 0 <= valueDiff <= 109

Difficulty: Hard

Tags: array, sliding window, sorting, bucket sort, ordered set

Rating: 91.39%

Solution Analysis

Key Insights

1. Bucket Strategy

   • Each bucket has a width of valueDiff + 1
   • Numbers that could satisfy the valueDiff condition will be in either:
     • The same bucket (difference ≤ valueDiff)
     • Adjacent buckets (need to check actual difference)

2. Bucket Size Choice

   • Width = valueDiff + 1 ensures:
     • Numbers in same bucket always satisfy valueDiff condition
     • Only need to check adjacent buckets
   • Example: if valueDiff = 3
     • Bucket ranges: […, -4 to -1], [0 to 3], [4 to 7], …

3. Sliding Window

   • Maintains indexDiff constraint using deletion
   • Only keeps buckets for elements within the window
   • Ensures O(min(n,k)) space complexity where k = indexDiff

Algorithm Deep Dive

1. Bucket Assignment

   bucket_id = nums[i] // w
   

   • Division by bucket width groups similar numbers
   • Integer division automatically handles bucket boundaries
   • Works for both positive and negative numbers

2. Three-way Check

   if bucket_id in bucket:  # Same bucket
       return True
   if (bucket_id - 1) in bucket and abs(nums[i] - bucket[bucket_id - 1]) < w:  # Left bucket
       return True
   if (bucket_id + 1) in bucket and abs(nums[i] - bucket[bucket_id + 1]) < w:  # Right bucket
       return True
   

   • Check same bucket: Guaranteed to satisfy valueDiff
   • Check adjacent buckets: Need explicit comparison
   • No need to check other buckets as difference would exceed valueDiff

3. Window Maintenance

   if i >= indexDiff:
       del bucket[nums[i - indexDiff] // w]
   

   • Removes elements outside indexDiff window
   • Maintains sliding window property
   • Ensures space efficiency

Complexity Analysis

1. Time Complexity: O(n)

   • Single pass through array
   • Each element:
     • Constant time bucket operations (hash table)
     • At most 3 bucket checks
     • One deletion operation

2. Space Complexity: O(min(n, indexDiff))

   • Bucket dictionary size limited by window size
   • Never exceeds array length or indexDiff
   • Efficient for small windows on large arrays

Why This Approach?

The bucket approach elegantly combines several optimization techniques:

• Spatial locality through bucketing
• Sliding window for index constraint
• Hash table for O(1) operations
• Minimal comparisons needed

This makes it superior to the O(n*k) naive approach or O(n log k) tree-based solutions for most practical inputs.

Solution

Here’s my Python solution to this problem:

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:
        if indexDiff < 0 or valueDiff < 0:
            return False
        
        # Each bucket will have range of valueDiff + 1
        bucket = {}
        w = valueDiff + 1
        
        for i in range(len(nums)):
            bucket_id = nums[i] // w
            
            # Check if there's already a number in the same bucket
            if bucket_id in bucket:
                return True
                
            if (bucket_id - 1) in bucket and abs(nums[i] - bucket[bucket_id - 1]) < w:
                return True
            if (bucket_id + 1) in bucket and abs(nums[i] - bucket[bucket_id + 1]) < w:
                return True
                
            bucket[bucket_id] = nums[i]
            
            # Remove bucket entry that's outside the window of indexDiff
            if i >= indexDiff:
                del bucket[nums[i - indexDiff] // w]
                
        return False