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 <= 109The key challenge in Contains Duplicate III is to determine whether two indices i and j exist such that their distance is within k and the difference between their values is at most t. A brute force comparison of nearby elements quickly becomes inefficient, so optimized strategies are required.
A common approach uses a sliding window combined with an ordered set (such as a balanced BST or TreeSet). As the window moves, we maintain only the last k elements and query the structure to check if a value within the range [nums[i] - t, nums[i] + t] already exists. This allows efficient range checks while keeping the window size bounded.
Another popular technique is bucket sorting, where numbers are mapped into buckets of size t + 1. If two numbers fall into the same or adjacent buckets within the sliding window, the condition may be satisfied. These strategies reduce unnecessary comparisons and maintain efficient lookups.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sliding Window with Ordered Set | O(n log k) | O(k) |
| Bucket Sort with Sliding Window | O(n) | O(k) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Time complexity O(n logk) - This will give an indication that sorting is involved for k elements.
Use already existing state to evaluate next state - Like, a set of k sorted numbers are only needed to be tracked. When we are processing the next number in array, then we can utilize the existing sorted state and it is not necessary to sort next overlapping set of k numbers again.
This approach uses a sliding window technique to maintain a set of the current window elements. TreeSet (or equivalent in other languages) is used to efficiently handle range-based queries within the window. By maintaining a set of elements within indexDiff, we can quickly check if there is a number within valueDiff of the current number.
Time complexity: O(n log k) where n is the length of the array and k is indexDiff, due to logarithmic time complexity of TreeSet operations.
Space complexity: O(k) since we store at most indexDiff elements in the set.
1import java.util.TreeSet;
2
3public class Solution {
4 public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
5 if (indexDiff <= 0 || valueDiff < 0) return false;
6 TreeSet<Long> set = new TreeSet<>();
7 for (int i = 0; i < nums.length; i++) {
8 long num = (long) nums[i];
9 Long floor = set.floor(num + valueDiff);
10 Long ceil = set.ceiling(num - valueDiff);
11 if ((floor != null && floor >= num) || (ceil != null && ceil <= num)) {
12 return true;
13 }
14 set.add(num);
15 if (i >= indexDiff)
16 set.remove((long) nums[i - indexDiff]);
17 }
18 return false;
19 }
20}The implementation uses a TreeSet to maintain elements within a sliding window of size indexDiff. For each element, we check for the existence of any number in the set that differs by at most valueDiff from the current number. The floor and ceiling methods efficiently find potential candidates within the set. After processing each element, we update the set by adding the current number and removing the one that falls out of the window.
This approach involves bucketing the numbers using their division by (valueDiff + 1). Each bucket can contain numbers that satisfy the valueDiff condition. We keep track of active buckets for indices falling within the indexDiff range.
Time complexity: O(n), where n is the number of elements, as each operation (insert, check, remove) is constant time on average.
Space complexity: O(k), due to the hash map's storage for at most k buckets.
1def contains_nearby_almost_duplicate(nums, indexDiff, valueDiff):
2Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Contains Duplicate III is considered a challenging problem that tests knowledge of sliding windows, ordered data structures, and hashing techniques. Variations of this question have appeared in interviews at large tech companies. It is especially useful for assessing a candidate's ability to optimize naive solutions.
Bucket sorting groups numbers into ranges so that values within t distance fall into the same or neighboring buckets. This reduces the need for expensive comparisons. Combined with a sliding window, it can achieve near O(n) time complexity.
An efficient solution uses a sliding window combined with an ordered set or balanced BST. This allows checking whether any element within the last k indices falls within the value range [nums[i] - t, nums[i] + t]. The approach keeps operations efficient while limiting comparisons to the active window.
Balanced search trees (like TreeSet) or ordered sets are commonly used because they support fast range queries. Another effective structure is a hash-based bucket map that groups numbers into ranges of size t + 1. Both structures help maintain efficient lookups within the sliding window.
This method uses bucketing similar to the Java implementation. By translating numbers into bucket indices based on the value size, we efficiently map and check potential candidates.