September 04, 2019

220. Contains Duplicate III

220. Contains Duplicate III

Sol 1. TreeSet (Binary Search Tree)

Time = O(nlogk), Space = O(k)

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            
            Integer ceil = set.ceiling(nums[i]);
            Integer floor = set.floor(nums[i]);
            
            if (ceil != null && ceil - (long) nums[i] <= t) {
                return true;
            }
            if (floor != null && (long) nums[i] - floor <= t) {
                return true;
            }
            
            set.add(nums[i]);
            if (set.size() > k) {
                set.remove(nums[i - k]);
            }
        }
        return false;
        
    }
}

Sol 2. Bucket

TBD

comments powered by Disqus