#220 Contains Duplicate III
frequently reported atNetflixAirbnbMicrosoftBloombergAmazonGoogle
the problem
In plain words
Return true if there are indices i ≠ j with |i − j| ≤ indexDiff and |nums[i] − nums[j]| ≤ valueDiff.
in nums = [1,2,3,1], indexDiff = 3, valueDiff = 0
out true
in nums = [1,5,9,1,5,9], indexDiff = 2, valueDiff = 3
out false
- 2 ≤ n ≤ 10⁵
- -10⁹ ≤ nums[i] ≤ 10⁹
- 1 ≤ indexDiff ≤ n
- 0 ≤ valueDiff ≤ 10⁹
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternSliding window (fixed size)Ordered map / set (floor & ceiling)Counting / bucket sort
Keep the last indexDiff values in a sorted window. For a new x, the only candidate that matters is the smallest window value ≥ x − valueDiff — ceiling finds it in O(log k).
solutions
From brute force to optimal
For each i, compare with the next indexDiff elements.
- Two loops with j − i ≤ indexDiff.
- Compare |nums[i] − nums[j]| as long.
k = min(n, indexDiff) comparisons per element — up to O(n²).
No extra structures.
class Solution { public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) { for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length && j - i <= indexDiff; j++) { if (Math.abs((long) nums[i] - nums[j]) <= valueDiff) return true; // long: no overflow } } return false; }}A TreeSet of the last indexDiff values; query ceiling(x − valueDiff).
- For each x: c = window.ceiling(x − valueDiff).
- If c ≤ x + valueDiff → true.
- Add x; remove nums[i − indexDiff] once the window is too big.
Each element does one ceiling, one add and one remove on a set of ≤ k values.
The window.
class Solution { public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) { TreeSet<Long> window = new TreeSet<>(); // values of the last indexDiff elements, sorted for (int i = 0; i < nums.length; i++) { long x = nums[i]; Long closest = window.ceiling(x - valueDiff); // smallest value >= x - valueDiff if (closest != null && closest <= x + valueDiff) return true; window.add(x); if (i >= indexDiff) window.remove((long) nums[i - indexDiff]); // slide the window } return false; }}Two values in the same bucket are always close enough; otherwise only the neighbour buckets can match.
- id = floorDiv(x, valueDiff + 1).
- Same bucket occupied → true; check buckets id − 1 and id + 1.
- Store x; evict the value that leaves the window.
O(1) average HashMap work per element.
At most k buckets — each holds one value, or we'd have returned true.
class Solution { public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) { long width = (long) valueDiff + 1; // two values in one bucket are always close enough Map<Long, Long> bucket = new HashMap<>(); // bucket id → the value in it for (int i = 0; i < nums.length; i++) { long x = nums[i]; long id = Math.floorDiv(x, width); // floorDiv handles negatives correctly if (bucket.containsKey(id)) return true; Long left = bucket.get(id - 1), right = bucket.get(id + 1); if (left != null && x - left <= valueDiff) return true; if (right != null && right - x <= valueDiff) return true; bucket.put(id, x); if (i >= indexDiff) bucket.remove(Math.floorDiv((long) nums[i - indexDiff], width)); } return false; }}in the room
How to say it in the interview
talk track
- Present the TreeSet version as the main answer — it's the BST lesson here. Offer buckets if asked for O(n).
traps
intoverflow inx - valueDifforx + valueDiffnear ±2³¹: uselong.- Plain
/instead ofMath.floorDivfor negative bucket ids (−1 / 3 is 0 in Java, but should be −1).
what they ask next
Follow-ups
Why does each bucket hold at most one value?
Two values in the same bucket differ by at most valueDiff, so the moment a second one arrives you return true. That's why a plain HashMap<Long, Long> of bucket id → value is enough.
Why check only buckets id − 1 and id + 1?
A value two or more buckets away differs by more than valueDiff, so it can never match. Only the neighbours can hold a close value.
before you submit
Edge cases to test
- Values near ±2³¹ →
x - valueDiffoverflows an int; do the maths in long. - valueDiff = 0 → you're looking for an equal value inside the window.
- Negative numbers with buckets → use
Math.floorDiv, not/.
practise next
Similar problems
- #219Contains Duplicate IIEasyin Sliding Window
- #217Contains DuplicateEasyin Hashing
- #729My Calendar IMediumin BST