We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Contains Duplicate III

Number: 220

Difficulty: Hard

Paid? No

Companies: Google, Yandex, Amazon, Adobe, Airbnb, Palantir Technologies

Problem Description

Given an integer array and two integers indexDiff and valueDiff, determine whether there exist two distinct indices i and j such that the absolute difference of their indices is no more than indexDiff and the absolute difference of their values is no more than valueDiff.

Key Insights

  • Use a sliding window of size indexDiff to ensure the index condition.
  • To efficiently check the value condition, maintain a data structure with near-ordering.
  • Bucket sort (or using an ordered set / BST) can help check for any element within [num - valueDiff, num + valueDiff] in O(1) average time.
  • Use a bucket size of (valueDiff + 1) to map numbers to buckets. Two numbers in the same or adjacent buckets may satisfy the condition.

Space and Time Complexity

Time Complexity: O(n) on average (each element is processed once and bucket operations take constant time on average). Space Complexity: O(min(n, indexDiff)) since we only store the current sliding window’s elements.

Solution

The solution leverages bucket sort along with a sliding window. We use a hash map to maintain buckets, where each bucket size is defined as (valueDiff + 1). For each element:

  1. Compute its bucket ID.
  2. Check if this bucket already has a number (this guarantees the value difference is within valueDiff).
  3. Check the adjacent buckets (bucket-1 and bucket+1) for potential candidates.
  4. Insert the current number into its bucket.
  5. Once the sliding window exceeds the size indexDiff, remove the element that falls outside the window. This approach ensures both conditions (index and value constraints) are met efficiently.

Code Solutions

Below are implementations in Python, JavaScript, C++, and Java.

class Solution:
    def containsNearbyAlmostDuplicate(self, nums, indexDiff, valueDiff):
        # Early return; bucket size is valueDiff + 1 to avoid division by zero when valueDiff is 0
        if valueDiff < 0:
            return False

        bucketSize = valueDiff + 1  # Bucket size ensures closer numbers fall in same or adjacent buckets
        buckets = {}  # Map bucket id to the number in that bucket

        for i, num in enumerate(nums):
            # Compute bucket id. For negative values, adjust bucket calculation.
            bucketId = num // bucketSize if num >= 0 else ((num + 1) // bucketSize - 1)

            # Check if current bucket already contains an element
            if bucketId in buckets:
                return True

            # Check the left adjacent bucket
            if (bucketId - 1 in buckets and abs(num - buckets[bucketId - 1]) < bucketSize):
                return True

            # Check the right adjacent bucket
            if (bucketId + 1 in buckets and abs(num - buckets[bucketId + 1]) < bucketSize):
                return True

            # Insert the current number into its bucket
            buckets[bucketId] = num

            # Maintain the sliding window of size indexDiff
            if i >= indexDiff:
                # Compute bucket id for the element to be removed
                removeNum = nums[i - indexDiff]
                removeBucketId = removeNum // bucketSize if removeNum >= 0 else ((removeNum + 1) // bucketSize - 1)
                del buckets[removeBucketId]

        return False
← Back to All Questions