Scale Engineer

Contains Duplicate III

Hard
#0208Time: O(n²) where n is the length of the array as we need to check every possible pairSpace: O(1) as we only use a constant amount of extra space4 companies
Patterns
Sliding Window
Algorithms
SortingBucket Sort
Data structures
ArrayOrdered Set
Companies
AirbnbYandexNetflixPalantir Technologies

Prompt

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, and

Return true if such pair exists or false otherwise.

 

Example 1:

Input: nums = [1,2,3,1], indexDiff = 3, valueDiff = 0
Output: true
Explanation: We can choose (i, j) = (0, 3).
We satisfy the three conditions:
i != j --> 0 != 3
abs(i - j) <= indexDiff --> abs(0 - 3) <= 3
abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0

Example 2:

Input: nums = [1,5,9,1,5,9], indexDiff = 2, valueDiff = 3
Output: false
Explanation: After trying all the possible pairs (i, j), we cannot satisfy the three conditions, so we return false.

 

Constraints:

  • 2 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • 1 <= indexDiff <= nums.length
  • 0 <= valueDiff <= 109

Approaches

3 approaches with complexity analysis and trade-offs.

Check every possible pair of indices (i,j) in the array and verify if they satisfy all three conditions.

Algorithm

  1. Iterate through each index i from 0 to n-1
  2. For each i, iterate through j from i+1 to n-1
  3. Check if |i-j| ≤ indexDiff
  4. Check if |nums[i] - nums[j]| ≤ valueDiff
  5. If both conditions are met, return true
  6. If no such pair is found, return false

Walkthrough

For each index i in the array, we check all possible indices j that come after i. For each pair, we verify:

  1. If i and j are different (always true in this case)
  2. If the absolute difference between indices (|i-j|) is less than or equal to indexDiff
  3. If the absolute difference between values (|nums[i] - nums[j]|) is less than or equal to valueDiff

Here's the implementation:

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++) {            if (Math.abs(i - j) <= indexDiff &&                 Math.abs((long)nums[i] - nums[j]) <= valueDiff) {                return true;            }        }    }    return false;}

Note: We use long for the value difference calculation to handle potential integer overflow cases.

Complexity

Time

O(n²) where n is the length of the array as we need to check every possible pair

Space

O(1) as we only use a constant amount of extra space

Trade-offs

Pros

  • Simple to implement

  • No extra space required

  • Works for all input cases

Cons

  • Very slow for large arrays

  • Inefficient as it checks all possible pairs

  • Not suitable for large inputs due to quadratic time complexity

Solutions

public class Solution {    public bool ContainsNearbyAlmostDuplicate(int[] nums, int k, int t) {        if (k <= 0 || t < 0) return false;        var index = new SortedList < int,            object > ();        for (int i = 0; i < nums.Length; ++i) {            if (index.ContainsKey(nums[i])) {                return true;            }            index.Add(nums[i], null);            var j = index.IndexOfKey(nums[i]);            if (j > 0 && (long) nums[i] - index.Keys[j - 1] <= t) {                return true;            }            if (j < index.Count - 1 && (long) index.Keys[j + 1] - nums[i] <= t) {                return true;            }            if (index.Count > k) {                index.Remove(nums[i - k]);            }        }        return false;    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem