DKodeTree Small Logo
DKodeTreeWhere logic takes root...!
Contains Duplicate III - Solution
Solutions and explanations
Link to Problem StatementView on GitHubWatch Video

Video Explanation

This approach uses a SortedSet to maintain a sliding window of up to indexDiff elements (ie.k).
Since the window is kept sorted, we can leverage binary search to efficiently check whether there's a number within valueDiff of the current number.
The algorithm iterates through nums and, for each number, checks whether there is a value within valueDiff in the current window.

  • If such a number is found, it returns True.
  • Otherwise, it adds the current number to the SortedSet and removes the leftmost (oldest) one when the window size exceeds indexDiff.

If the entire array is processed without finding such a pair, the function returns False.

from sortedcontainers import SortedSet

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:
        if indexDiff <= 0 or valueDiff < 0:
            return False

        window = SortedSet() # Maintain a sorted sliding window

        left = 0
        for num in nums:
            # Find the smallest number in the window that is ≥ (num - valueDiff), as a potential nearby almost duplicate
            pos = window.bisect_left(num - valueDiff) 

            # Check if that number is within valueDiff of current num
            if pos < len(window) and abs(num - window[pos]) <= valueDiff:
                return True

            window.add(num)
            # Ensure window size does not exceed indexDiff
            if len(window) > indexDiff:
                window.remove(nums[left])
                left += 1

        return False

Complexity Analysis

Here, n is the input size, and k is the size of the sliding window (ie. indexDiff).

  • Time Complexity: O(n log k)
    • Each insertion and removal in the SortedSet takes O(log k), and we perform these operations n times, making the time complexity O(n log k).
  • Space Complexity: O(k)
    • The SortedSet window holds at most k elements at any time.

This approach groups numbers into buckets of size valueDiff + 1 using a hash map (dictionary), while maintaining a sliding window of size indexDiff.
For each number, it checks the current and adjacent buckets for any number within valueDiff.

  • If such a number is found, it returns True.
  • Otherwise, it adds the current number to its bucket and removes the number that falls outside the sliding window when the window exceeds indexDiff.

Finally, if no such pair is found after processing all elements, the function returns False.

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:
        if indexDiff <= 0 or valueDiff < 0:
            return False

        buckets = collections.defaultdict(int)      # Hashmap to store {bucket_id -> num} in the sliding window
        bucket_size = valueDiff + 1                 # Ensures numbers in the same bucket are within valueDiff

        left = 0
        for right, num in enumerate(nums):
            bucket_id = num // bucket_size      # Python automatically floors integer division for negative numbers
            
            if bucket_id in buckets:            # Check if the current bucket already has a number
                return True
            
            # Check adjacent buckets for numbers within valueDiff of the current num, as they may be close enough to satisfy the condition
            for adj_id in (bucket_id - 1, bucket_id + 1):   
                if adj_id in buckets and abs(num - buckets[adj_id]) <= valueDiff:
                    return True

            buckets[bucket_id] = num    # Add current num to its bucket in the sliding window

            # Ensure window size does not exceed indexDiff, by removing the oldest number if needed (sliding window)
            if right - left >= indexDiff:
                old_num = nums[left]
                old_bucket_id = old_num // bucket_size
                del buckets[old_bucket_id]
                left += 1

        return False

Complexity Analysis

Here, n is the input size, and k is the size of the sliding window (ie. indexDiff).

  • Time Complexity: O(n)
    • Each insertion and removal in the bucket (hash map) takes O(1) on average. In the worst case, we perform these operations for each of the n elements, resulting in a total time complexity of O(n).
  • Space Complexity: O(k)
    • The bucket window (hashmap) holds at most k elements at any time due to the sliding window constraint.