Watch 10 video solutions for Contains Duplicate III, a hard level problem involving Array, Sliding Window, Sorting. This walkthrough by NeetCode has 770,501 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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, andReturn 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] <= 1091 <= indexDiff <= nums.length0 <= valueDiff <= 109Problem Overview: Given an integer array, determine whether two different indices i and j exist such that |i - j| ≤ k and |nums[i] - nums[j]| ≤ t. The challenge is enforcing both the index distance and value distance constraints efficiently without checking every pair.
Approach 1: Sliding Window with TreeSet (O(n log k) time, O(k) space)
This approach maintains a sliding window of size k containing the last k elements while iterating through the array. An ordered structure like TreeSet (Java) or a balanced sorted container is used so you can quickly find the closest numbers to the current value. For each element nums[i], search the set for the smallest number greater than or equal to nums[i] - t. If that candidate is ≤ nums[i] + t, the condition is satisfied. Insert the current value into the set and remove the element that slides out when the window exceeds size k. Ordered lookup and insertion take O(log k), giving total O(n log k) time with O(k) space. This technique combines sliding window logic with an ordered set to enforce both constraints efficiently.
Approach 2: Bucketing Technique (O(n) time, O(n) space)
The bucket method achieves linear time by grouping numbers into ranges of width t + 1. If two numbers differ by at most t, they must fall into either the same bucket or adjacent buckets. For each element, compute its bucket ID using integer division. First check whether the current bucket already contains a number. Then check the neighboring buckets because their values could still be within distance t. Store the current number in its bucket and maintain the k-sized window by removing the bucket corresponding to nums[i - k]. Each lookup, insertion, and deletion is constant time using a hash map, producing O(n) time and O(n) space. This approach relies on value partitioning rather than ordering and is closely related to bucket sort ideas applied to an array traversal.
Recommended for interviews: The sliding window with an ordered set is often the expected solution because it demonstrates understanding of balanced search trees and range queries. The bucket approach is more optimal at O(n) but requires a key insight about bucket width and careful handling of negative numbers and overflow. Showing the TreeSet solution first proves you understand the constraint interaction, while implementing the bucket technique signals stronger algorithmic intuition.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window with TreeSet | O(n log k) | O(k) | General interview solution when ordered range queries are easy to implement |
| Bucketing Technique | O(n) | O(n) | Best performance when constant-time hashing is available and bucket logic is implemented carefully |