Contains Duplicate III - Problem

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
  • abs(nums[i] - nums[j]) <= valueDiff

Return true if such pair exists or false otherwise.

Input & Output

Example 1 — Basic Case
$ Input: nums = [1,3,4,7,9], indexDiff = 3, valueDiff = 2
Output: true
💡 Note: Indices 1 and 2: abs(1-2) = 1 ≤ 3 and abs(3-4) = 1 ≤ 2, both conditions satisfied
Example 2 — No Valid Pair
$ Input: nums = [1,5,9,13], indexDiff = 2, valueDiff = 3
Output: false
💡 Note: No pair of indices satisfies both index difference and value difference constraints
Example 3 — Edge Case
$ Input: nums = [1,2], indexDiff = 1, valueDiff = 0
Output: false
💡 Note: abs(1-2) = 1 > 0, so no valid pair exists with valueDiff = 0

Constraints

  • 2 ≤ nums.length ≤ 2 × 104
  • -231 ≤ nums[i] ≤ 231 - 1
  • 1 ≤ indexDiff ≤ nums.length
  • 0 ≤ valueDiff ≤ 231 - 1

Visualization

Tap to expand
Contains Duplicate III: Find pairs within constraints1347901234indexDiff = 3, valueDiff = 2Check indices 1,2: abs(1-2) = 1 ≤ 3 ✓Check values: abs(3-4) = 1 ≤ 2 ✓Output: true
Understanding the Visualization
1
Input
Array with indexDiff and valueDiff constraints
2
Process
Find pair satisfying both index and value differences
3
Output
Return true if such pair exists
Key Takeaway
🎯 Key Insight: Use bucket sort to group values that are guaranteed to satisfy the value difference constraint
Asked in
Google 15 Amazon 12 Facebook 8 Microsoft 6
85.0K Views
Medium Frequency
~25 min Avg. Time
1.5K Likes
Ln 1, Col 1
Smart Actions
💡 Explanation
AI Ready
💡 Suggestion Tab to accept Esc to dismiss
// Output will appear here after running code
Code Editor Closed
Click the red button to reopen