DSA problem
Contains Duplicate III
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, and abs(nums[i] - nums[j]) <= valueDiff. Return true if such a pair exists; otherwise return false.
A brute force checks every pair within the index window, costing O(n * indexDiff). A balanced BST or TreeSet can answer floor/ceiling queries for the current sliding window in O(log indexDiff) per element, giving O(n log indexDiff) total — already strong.
The bucket-sort approach turns the value condition into a hash table lookup. Partition the integer line into buckets of width t + 1 (where t = valueDiff). The bucket containing a number x is x // (t + 1) using floor division (use Math.floor in JS/TS or arithmetic care in Java/C++ to handle negatives correctly — any two numbers within the same bucket differ by at most t). Two numbers within the same bucket are guaranteed close enough in value. Two numbers in adjacent buckets may or may not be close — verify with an explicit difference check.
Maintain a sliding window of size indexDiff over the array. For each nums[i], compute its bucket id; if the bucket already contains an element, return true (same-bucket numbers always satisfy the value diff). Otherwise check the two adjacent buckets and verify their stored value is within t. Insert nums[i] into its bucket. When the window grows past indexDiff, evict the element at index i - indexDiff - 1 from its bucket. The algorithm runs in O(n) amortized time, since each element is inserted and removed exactly once.
Examples
nums = [1,2,3,1], indexDiff = 3, valueDiff = 0truenums = [1,5,9,1,5,9], indexDiff = 2, valueDiff = 3falsenums = [-2,3], indexDiff = 1, valueDiff = 5trueConstraints
- 2 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- 1 <= indexDiff <= nums.length
- 0 <= valueDiff <= 10^9
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.