Understand the problem:
The naive solution is to maintain a sliding window with size k, when we add an element nums[i], compare the nums[i] with each element in the window. If it is less or equal to t, return true. We return true because the distance between i and each element in the window must be less or equal to k. The complexity of this solution would be O(nk).
We could use a treeSet to improve the complexity. The treeSet is essentially a balanced binary search tree. We put k elements in the treeSet, which is a sliding window. So when we insert an element to the treeSet, we need to remove one from the end.
So the basic idea is for each element nums[i], we check if there is any element between [nums[i] - t, nums[i] + t]. If yes, return true.
Code (Java):
public class Solution { public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) { if (nums == null || nums.length <= 1 || k <= 0 || t < 0) { return false; } TreeSet<Integer> treeSet = new TreeSet<>(); for (int i = 0; i < nums.length; i++) { Integer floor = treeSet.floor(nums[i] + t); Integer ceil = treeSet.ceiling(nums[i] - t); if ((floor != null && floor >= nums[i]) || (ceil != null && ceil <= nums[i])) { return true; } treeSet.add(nums[i]); if (i >= k) { treeSet.remove(nums[i - k]); } } return false; } }
Very elegant answer!!!.
ReplyDeleteIt is failing for the input [-2147483648,-2147483647]
3
3
-2147483648 is the MINIMUM_VALUE and 2147483647 is the MAX_VALUE that an 32-bit int variable can hold. Summation and substraction operations on those values lead to roll overs. (e.g. 2147483647+1 will be rolled over to -2147483648). For this code, operations +t and -t causes the same problem. So TreeSet should consist of variables, thus floor and ceiling values should be Long instead of Integer.
Delete