Reference: LeetCode
Difficulty: Medium

Problem

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

Example:

1
2
3
4
5
6
7
8
9
10
11
Input: nums = [1,2,3,1], k = 3, t = 0
Output: true

Input: nums = [1,0,1,1], k = 1, t = 2
Output: true

Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

Input: nums = [-1,2147483647], k = 1, t = 2147483647
Output: false

Analysis

Tree Set

Based on the solution in Contains Duplicate II, we use a tree set to keep k elements in ascending order.

Then we find the closest elements of nums[i]. We do binary search for value nums[i] to find the floor and ceiling elements, and compare them with nums[i] to see if the requirement is satisfied.

Note:

  • At the beginning, the tree set is empty.
  • Use Long type to solve the overflow problem.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
  int n = nums.length;
  TreeSet<Long> window = new TreeSet<>();
  for (int i = 0; i < n; ++i) {
    long val = (long) nums[i];
    // find two closest elements of val
    Long pred = window.floor(val); // actually binary search
    if (pred != null && val - pred <= t) return true;
    Long succ = window.ceiling(val);
    if (succ != null && succ - val <= t) return true;
    // add & remove
    window.add(val); // takes O(logN)
    if (window.size() > k) {
      window.remove((long) nums[i - k]); // takes O(logN)
    }
  }
  return false;
}

Time: $O(N\log{(\min(N, k))})$
Space: $O(\min(N, k))$