LeetCode - Contains Duplicate III
Problem description
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:
1
2
Input: nums = [1,2,3,1], k = 3, t = 0
Output: true
Example 2:
1
2
Input: nums = [1,0,1,1], k = 1, t = 2
Output: true
Example 3:
1
2
Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false
Analysis
The first thought is to use TreeSet to save a sliding window of size k, and check the next item’s value using floor and ceiling function of TreeSet.
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
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
TreeSet<Integer> treeSet = new TreeSet<>();
for (int i = 0; i < nums.length; i++){
int v = nums[i];
if (treeSet.size() != 0){
Integer floor = treeSet.floor(v);
Integer ceiling = treeSet.ceiling(v);
if ((floor != null && Math.abs((long)floor - v) <= t) || (ceiling != null && Math.abs((long)ceiling - v) <= t))
{
return true;
}
}
treeSet.add(nums[i]);
if (treeSet.size() > k){
treeSet.remove(nums[i-k]);
}
}
return false;
}
}
And the standard solution from LeetCode avoid the long part, which is wrong for this test case:
1
2
3
[2147483646,2147483647]
1
2
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) {
TreeSet<Integer> set = new TreeSet<>();
for (int i = 0; i < nums.length; ++i) {
// Find the successor of current element
Integer s = set.ceiling(nums[i]);
if (s != null && s <= nums[i] + t) return true; // overflow
// Find the predecessor of current element
Integer g = set.floor(nums[i]);
if (g != null && nums[i] <= g + t) return true; // overflow
set.add(nums[i]);
if (set.size() > k) {
set.remove(nums[i - k]);
}
}
return false;
}
What to improve
- the floor and ceiling function may return null. need to use Integer not int.
- be careful about the overflow of Integer.