Problem

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

OR

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.

Examples

Example 1:

1
2
3
4
5
6
7

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:

1
2
3

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.

Solution

Method 1 - Using TreeSet and Sliding Window

To solve the problem, we can use a sliding window approach and a data structure that allows efficient insertion, deletion, and lookup. A TreeSet provides these capabilities with logarithmic time complexity for each operation, making it a good choice for this problem.

Approach

  1. Use a TreeSet to maintain a sliding window of indexDiff or k size.
  2. For each element in nums:
    • Use TreeSet.floor() and TreeSet.ceiling() to find the nearest elements within the valueDiff or t.
    • If any such element is found, return true.
    • Maintain the sliding window by adding the current element to the set and removing the element that is indexDiff or k positions before the current index.

Lets see what floor and ceiling mean.

1
2

floor(x) = Largest element <= to the x.
ceiling(x) = Smallest element >= to the x.

So, if TreeSet has following elements:

1

set = [1, 2, 4, 5]

Then, here are floor and ceiling of 3:

1
2

floor(3) = 2
ceiling(3) = 4

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

public class Solution {

	public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
		if (nums == null || nums.length < 2 || k < 1 || t < 0) {
			return false;
		}

		// TreeSet to maintain the sliding window of `k` size
		TreeSet<Integer> set = new TreeSet<>();

		for (int i = 0; i < nums.length; i++) {
			int num = nums[i];

			// Check the floor within the t range
			Integer floor = set.floor(num);

			if (floor != null && Math.abs(num - floor)  <= t) {
				return true;
			}

			// Check the ceiling within the t range
			Integer ceiling = set.ceiling(num);

			if (ceiling != null && Math.abs(ceiling - num)  <= t) {
				return true;
			}

			set.add(num);

			// Maintain the sliding window by removing the element that is `k` positions before the current index
			if (i >= k) {
				set.remove(nums[i - k]);
			}
		}

		return false;
	}
}

Complexity

  • ⏰ Time complexity: O(n log k) where n is the length of the array and k is indexDiff. Because, we check each numbers floors and ceils, then add it to set, which takes log k, as we only store k elements in Treeset, and we do it for n elements, hence O(n log k)
  • 🧺 Space complexity: O(k)