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.
O(n log k) time O(k) space solution 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 public class Solution { public boolean containsNearbyAlmostDuplicate (int [] nums, int k, int t) { if (nums == null || nums.length == 0 || k <= 0 ) { return false ; } TreeSet<Integer> set = new TreeSet<>(); for (int i = 0 ; i < nums.length; i++) { int cur = nums[i]; Integer floor = set.floor(cur + t); if (floor != null && floor >= cur) { return true ; } Integer ceil = set.ceiling(cur - t); if (ceil != null && ceil <= cur) { return true ; } set.add(cur); if (set.size() > k) { set.remove(nums[i - k]); } } return false ; } }
O(n) time using Buckets 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 public class Solution { private long getId (long num, long bucket) { return num < 0 ? (num + 1 )/bucket - 1 : num / bucket; } public boolean containsNearbyAlmostDuplicate (int [] nums, int k, int t) { if (nums == null || nums.length == 0 || k <= 0 || t < 0 ) { return false ; } Map<Long, Long> map = new HashMap<>(); long bucket = t + 1 ; for (int i = 0 ; i < nums.length; i++) { long id = getId(nums[i], bucket); if (map.containsKey(id)) { return true ; } if (map.containsKey(id - 1 ) && (Math.abs(nums[i] - map.get(id - 1 )) < bucket)) { return true ; } if (map.containsKey(id + 1 ) && (Math.abs(nums[i] - map.get(id + 1 )) < bucket)) { return true ; } map.put(id, (long ) nums[i]); if (map.size() > k) { map.remove(getId(nums[i - k], bucket)); } } return false ; } }