Contains Duplicate III
Understanding the Problem
This is a harder variant of Contains Duplicate with two proximity constraints. Instead of repeated values, we need two elements that are close both in position (at most indexDiff indices apart) and in value (at most valueDiff apart).
A sliding window frames the problem: at each index, the candidates for a match are the previous indexDiff elements. The question at every step is whether any of those candidates is within valueDiff of the current value, and the challenge is answering it efficiently as the window slides.
The window needs a data structure that supports three operations efficiently: insert an element, delete the element that slides out, and query whether any stored value is within valueDiff of a given value. Each approach below picks a different structure for this job, with a different time complexity.
Key Constraints:
2 <= nums.length <= 10^5→ With n up to 100,000, O(n^2) is too slow. Even O(n * indexDiff) degenerates to O(n^2) when indexDiff is close to n. We need O(n log n) or O(n).-10^9 <= nums[i] <= 10^9→ Values span a wide range. We need to handle negative numbers carefully, especially with bucket-based approaches where floor division behaves differently for negatives.0 <= valueDiff <= 10^9→ When valueDiff is 0, we are looking for exact duplicates within the indexDiff range (essentially Contains Duplicate II). When valueDiff is large, almost any pair within the window qualifies.
Approach 1: Brute Force
Intuition
For each element, compare it with every element up to indexDiff positions ahead. If any pair has values within valueDiff, return true. No extra data structure is needed.
One detail matters: with values as large as 10^9 in magnitude, the difference nums[i] - nums[j] can reach 2 * 10^9, which overflows a 32-bit int. The subtraction needs a 64-bit type in languages with fixed-width integer arithmetic.
Algorithm
- For each index
ifrom 0 to n - 1: - For each index
jfromi + 1tomin(i + indexDiff, n - 1): - If
abs(nums[i] - nums[j]) <= valueDiff, return true. - If no pair is found after all comparisons, return false.
Visualization and Code
Loading animation...
- Time Complexity: O(n * min(n, indexDiff)). For each of the n elements, we check up to indexDiff neighbors. In the worst case where indexDiff >= n, this becomes O(n^2).
- Space Complexity: O(1). Only loop variables, no extra data structures.
The inner loop rescans up to indexDiff elements at every index and discards everything it learned on the previous iteration. A sorted structure over the current window can answer "is any value within valueDiff?" without a fresh scan.
Approach 2: Sorted Set (TreeSet / Balanced BST)
Intuition
Keeping the window elements in sorted order turns the proximity check into a single lookup: for a new element x, find the closest stored value to x and compare.
A balanced BST (like Java's TreeSet) supports this. The ceiling(x - valueDiff) operation finds the smallest element in the set that is greater than or equal to x - valueDiff. If that element exists and is also less than or equal to x + valueDiff, it is within valueDiff of x. This one check is sufficient: every other element is either below x - valueDiff, and therefore out of range, or at least as large as the ceiling, so if the ceiling itself exceeds x + valueDiff, nothing in the set is in range.
The full algorithm slides a window of size indexDiff across the array, maintaining the sorted set. For each new element, query the set, then insert the element and remove the one that fell out of the window.
Algorithm
- Create an empty sorted set (TreeSet).
- For each index
ifrom 0 to n - 1: - Query the set for the smallest element >=
nums[i] - valueDiff(the "ceiling"). - If that ceiling exists and is <=
nums[i] + valueDiff, return true. - Insert
nums[i]into the set. - If the set size exceeds
indexDiff, removenums[i - indexDiff](the element that just left the window). - If no pair is found after processing all elements, return false.
Visualization and Code
Loading animation...
- Time Complexity: O(n log(min(n, indexDiff))) with a balanced BST. We process each of the n elements once, and each set operation (ceiling, insert, remove) takes O(log k) where k is the window size, bounded by indexDiff. With a sorted array instead of a BST, lookups stay O(log k) but each insert or remove shifts elements, so the worst case becomes O(n * min(n, indexDiff)).
- Space Complexity: O(min(n, indexDiff)). The sorted structure holds at most indexDiff elements at any time.
Every sorted-set operation still carries a logarithmic cost. The bucket technique below replaces the ordered structure with a hash map and answers the proximity question with O(1) lookups.
Approach 3: Bucket Sort (Optimal)
Intuition
Divide the number line into buckets of width w = valueDiff + 1. Bucket 0 holds values 0 through valueDiff, bucket 1 holds valueDiff + 1 through 2 * valueDiff + 1, and so on.
If two values land in the same bucket, their difference is at most w - 1 = valueDiff, a guaranteed match with no further computation. If two values land in adjacent buckets, they might be within valueDiff of each other, so a direct value comparison settles it. If two values are in buckets more than one apart, they differ by more than valueDiff and can be skipped.
So for each new element, we compute its bucket ID and make three O(1) hash map lookups: does the same bucket already have an element, and does the left or right neighbor bucket have an element within valueDiff? Combined with the sliding window for indexDiff, the whole scan is O(n).
Negative numbers need care. Bucket IDs require floor division (rounding toward negative infinity), but integer division in many languages truncates toward zero. For negative num, the formula (num + 1) / w - 1 converts truncating division into the floor result. Languages with native floor division, such as Python's // operator or Math.floor in JavaScript, need no adjustment.
Values two or more buckets apart differ by at least w + 1, which exceeds valueDiff, so skipping them never misses a match. The hash map stores at most one value per bucket: a second value mapping to an occupied bucket returns true before it is ever inserted. This single-occupancy invariant also makes window removal safe, because the element leaving the window is the only value its bucket holds.
Algorithm
- Set bucket width
w = valueDiff + 1. - Create an empty hash map to store
bucket_id -> valuemappings. - For each index
ifrom 0 to n - 1: - Compute the bucket ID for
nums[i]using floor division. - If the bucket already has an element, return true (same bucket guarantees match).
- Check the left neighbor bucket (
bucketId - 1): if it has an element andabs(nums[i] - that element) <= valueDiff, return true. - Check the right neighbor bucket (
bucketId + 1): if it has an element andabs(nums[i] - that element) <= valueDiff, return true. - Insert
nums[i]into its bucket. - If
i >= indexDiff, remove the bucket fornums[i - indexDiff](slide the window). - If no pair is found after all elements, return false.
Visualization and Code
Loading animation...
- Time Complexity: O(n). We process each element once. For each element, we do a constant number of hash map operations (3 lookups, 1 insert, at most 1 delete), each O(1) amortized.
- Space Complexity: O(min(n, indexDiff)). The hash map holds at most indexDiff buckets at any time.