The problem
Given nums, indexDiff k and valueDiff t, decide if two indices i ≠ j exist with |i − j| ≤ k and |nums[i] − nums[j]| ≤ t.
Stuck? Reveal hints one at a time
How to approach it
- 1Bucket trick: bucketId = floor(value / (t + 1)). Values in the SAME bucket are automatically within t.
- 2For each element: check its own bucket (hit → true), and check the two neighbor buckets with an explicit |diff| ≤ t test.
- 3Insert the value into its bucket; evict the element k+1 positions back to keep the window.
- 4No hit after the scan → false.
Key insight
Buckets of width t+1 discretize "within t": same bucket is a guaranteed hit, adjacent buckets are the only near-misses to verify — everything else is provably too far.
The solution
Watch out for
- Floor division must round toward −∞ for negatives — Python // does; JS needs Math.floor, not truncation.
- The ordered-set (SortedList / TreeSet) solution is O(n log k) and easier to defend under pressure.