Return true if there are indexes i ≠ j with |i − j| ≤ indexDiff and |nums[i] − nums[j]| ≤ valueDiff.
Before you code
Keep the last indexDiff values in some structure. For a new value x, which single question about that structure decides whether a close value exists?
Hints
- Keep the window's values in an ordered set, such as SortedList in Python or TreeSet in Java.
- For each x, find the smallest value at least x − valueDiff. If it exists and is at most x + valueDiff, return true.
- Add x, and remove the value that falls out of the window. Total O(n log k).
- Afterwards, try the O(n) alternative: buckets of width valueDiff + 1 in a hash map, checking the same and neighboring buckets.
Production & complexity notes
When solving Contains duplicate III on LeetCode (hard), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Choosing an ordered structure to reinforce the underlying pattern.
What it practices
Ordered-set queries over a sliding window, from Choosing an ordered structure.