Contains Duplicate III
Contains Duplicate III is a hard arrays & hashing problem solved with the sliding window · hash map pattern.
The best approach, optimal (buckets of width valuediff + 1), runs in O(n) time and O(k) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force up.
Problem
You are given an integer array nums and two integers indexDiff and valueDiff. Decide whether there are two different indices i and j such that:
|i - j| <= indexDiff, and|nums[i] - nums[j]| <= valueDiff.
Return true if such a pair exists, otherwise false.
Examples
Example 1
- Input
nums = [10, 3, 15, 6], indexDiff = 2, valueDiff = 3- Output
true- Why
- Indices 1 and 3 are 2 apart and |3 - 6| = 3, which is within valueDiff.
Example 2
- Input
nums = [1, 9, 17, 25], indexDiff = 3, valueDiff = 7- Output
false- Why
- Every pair of values differs by at least 8.
Example 3
- Input
nums = [-4, 20, 0, -5], indexDiff = 2, valueDiff = 1- Output
false- Why
- -4 and -5 differ by 1, but their indices are 3 apart, more than indexDiff.
Constraints
2 <= nums.length <= 10^5-10^9 <= nums[i] <= 10^91 <= indexDiff <= nums.length0 <= valueDiff <= 10^9
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 18 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n · indexDiff) | O(1) |
| Sorted window | O(n log k) | O(k) |
| Optimal (buckets of width valueDiff + 1) | O(n) | O(k) |
1Brute force
O(n · indexDiff)Each element is compared with up to indexDiff later elements.O(1)Only loop indices.For each index, compare it with the next indexDiff elements and check whether any value is within valueDiff.
- For i from 0 to n - 1, for j from i + 1 to min(n - 1, i + indexDiff).
- If |nums[i] - nums[j]| <= valueDiff (computed in 64 bits), return true.
- Return false.
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
int n = nums.length;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n && j <= i + indexDiff; j++) {
if (Math.abs((long) nums[i] - nums[j]) <= valueDiff) return true;
}
}
return false;
}
}class Solution:
def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:
n = len(nums)
for i in range(n):
for j in range(i + 1, min(n, i + indexDiff + 1)):
if abs(nums[i] - nums[j]) <= valueDiff:
return True
return Falseclass Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
int n = nums.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n && j <= i + indexDiff; j++) {
if (llabs((long long) nums[i] - nums[j]) <= valueDiff) return true;
}
}
return false;
}
};function containsNearbyAlmostDuplicate(nums, indexDiff, valueDiff) {
const n = nums.length;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n && j <= i + indexDiff; j++) {
if (Math.abs(nums[i] - nums[j]) <= valueDiff) return true;
}
}
return false;
}2Sorted window
O(n log k)Each step does a search, an insert and a delete on a balanced tree of at most k = indexDiff values.O(k)The window holds at most indexDiff values.Keep the last indexDiff values in a sorted structure. For the current value x, find the smallest stored value that is at least x - valueDiff. If it exists and is at most x + valueDiff, the answer is true. Then add x and drop the value that just left the window.
- For each index i with value x:
- Find the ceiling of x - valueDiff in the window; if it is <= x + valueDiff, return true.
- Insert x. If the window holds more than indexDiff values, remove nums[i - indexDiff].
- Return false at the end.
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
TreeSet<Long> window = new TreeSet<>();
for (int i = 0; i < nums.length; i++) {
long x = nums[i];
Long ceil = window.ceiling(x - valueDiff);
if (ceil != null && ceil <= x + valueDiff) return true;
window.add(x);
if (i >= indexDiff) window.remove((long) nums[i - indexDiff]);
}
return false;
}
}class Solution:
def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:
window: List[int] = [] # kept sorted
for i, x in enumerate(nums):
pos = bisect.bisect_left(window, x - valueDiff)
if pos < len(window) and window[pos] <= x + valueDiff:
return True
bisect.insort(window, x)
if i >= indexDiff:
window.pop(bisect.bisect_left(window, nums[i - indexDiff]))
return Falseclass Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
set<long long> window;
for (int i = 0; i < (int) nums.size(); i++) {
long long x = nums[i];
auto it = window.lower_bound(x - valueDiff);
if (it != window.end() && *it <= x + valueDiff) return true;
window.insert(x);
if (i >= indexDiff) window.erase((long long) nums[i - indexDiff]);
}
return false;
}
};function containsNearbyAlmostDuplicate(nums, indexDiff, valueDiff) {
const window = []; // kept sorted
const lowerBound = (v) => {
let lo = 0, hi = window.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (window[mid] < v) lo = mid + 1; else hi = mid;
}
return lo;
};
for (let i = 0; i < nums.length; i++) {
const x = nums[i];
const pos = lowerBound(x - valueDiff);
if (pos < window.length && window[pos] <= x + valueDiff) return true;
window.splice(lowerBound(x), 0, x);
if (i >= indexDiff) window.splice(lowerBound(nums[i - indexDiff]), 1);
}
return false;
}3Optimal (buckets of width valueDiff + 1)
O(n)Each element does a constant number of hash map operations.O(k)The map holds at most indexDiff buckets, one per value in the window.Split the number line into buckets of width w = valueDiff + 1, so bucket id = floor(x / w). Two values in the same bucket differ by at most valueDiff, so a second value in a bucket means true. Values in buckets further than one apart differ by more than valueDiff, so only the two neighbouring buckets need a real check. Each bucket holds at most one value from the window, so a hash map from bucket id to value is enough.
- w = valueDiff + 1 (as a 64-bit number).
- For each index i with value x, id = floorDiv(x, w).
- If the map has id, return true.
- If the map has id - 1 with |x - value| <= valueDiff, or id + 1 with the same test, return true.
- Store map[id] = x. If i >= indexDiff, remove the bucket of nums[i - indexDiff].
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
long w = (long) valueDiff + 1;
Map<Long, Long> buckets = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
long x = nums[i];
long id = Math.floorDiv(x, w);
if (buckets.containsKey(id)) return true;
Long left = buckets.get(id - 1);
if (left != null && x - left <= valueDiff) return true;
Long right = buckets.get(id + 1);
if (right != null && right - x <= valueDiff) return true;
buckets.put(id, x);
if (i >= indexDiff) buckets.remove(Math.floorDiv((long) nums[i - indexDiff], w));
}
return false;
}
}class Solution:
def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:
w = valueDiff + 1
buckets: Dict[int, int] = {}
for i, x in enumerate(nums):
bid = x // w
if bid in buckets:
return True
if bid - 1 in buckets and x - buckets[bid - 1] <= valueDiff:
return True
if bid + 1 in buckets and buckets[bid + 1] - x <= valueDiff:
return True
buckets[bid] = x
if i >= indexDiff:
del buckets[nums[i - indexDiff] // w]
return Falseclass Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
long long w = (long long) valueDiff + 1;
auto bucketOf = [w](long long x) { return x >= 0 ? x / w : (x + 1) / w - 1; };
unordered_map<long long, long long> buckets;
for (int i = 0; i < (int) nums.size(); i++) {
long long x = nums[i];
long long id = bucketOf(x);
if (buckets.count(id)) return true;
auto left = buckets.find(id - 1);
if (left != buckets.end() && x - left->second <= valueDiff) return true;
auto right = buckets.find(id + 1);
if (right != buckets.end() && right->second - x <= valueDiff) return true;
buckets[id] = x;
if (i >= indexDiff) buckets.erase(bucketOf(nums[i - indexDiff]));
}
return false;
}
};function containsNearbyAlmostDuplicate(nums, indexDiff, valueDiff) {
const w = valueDiff + 1;
const buckets = new Map();
for (let i = 0; i < nums.length; i++) {
const x = nums[i];
const id = Math.floor(x / w);
if (buckets.has(id)) return true;
if (buckets.has(id - 1) && x - buckets.get(id - 1) <= valueDiff) return true;
if (buckets.has(id + 1) && buckets.get(id + 1) - x <= valueDiff) return true;
buckets.set(id, x);
if (i >= indexDiff) buckets.delete(Math.floor(nums[i - indexDiff] / w));
}
return false;
}Edge cases to test
- valueDiff = 0: the question becomes "is there an exact duplicate within indexDiff"
- Values at both ends of the range, where differences overflow 32-bit ints
- Negative values: bucket ids must round down, not toward zero
- indexDiff equal to the array length
Hints
Hint 1
Only the last indexDiff elements matter when you are at index i.
Hint 2
Among those, you only need the smallest value that is >= nums[i] - valueDiff. A sorted structure finds it fast.
Hint 3
Put values into buckets of width valueDiff + 1. Two values in the same bucket always qualify; only the neighbouring buckets need a real check.
FAQ
What is the best time complexity for Contains Duplicate III?
Optimal (buckets of width valueDiff + 1) runs in O(n) time and O(k) extra space. Each element does a constant number of hash map operations.
Which pattern does Contains Duplicate III use?
It is a arrays & hashing problem that uses the sliding window · hash map pattern. Other problems with the same pattern: Number of Substrings Containing All Three Characters, Minimum Window Substring, Longest Substring with At Most K Distinct Characters.
Is there a brute force solution for Contains Duplicate III?
Yes. Brute force takes O(n · indexDiff) time and O(1) space. For each index, compare it with the next indexDiff elements and check whether any value is within valueDiff.
Which edge cases should I test for Contains Duplicate III?
valueDiff = 0: the question becomes "is there an exact duplicate within indexDiff"; Values at both ends of the range, where differences overflow 32-bit ints; Negative values: bucket ids must round down, not toward zero; indexDiff equal to the array length.