Contains Duplicate III

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.

Analysis

• Use TreeSet data structure (binary search tree)
• Maintain tree: O(NlgK)
• Check value: O(lgK)

Code

public boolean containsNearbyAlmostDuplicate(int[] nums, intk, int t){
    if(nums.length<2 || k==0) {return false;}
    //use long to prevent overflow
    TreeSet<Long> set = new TreeSet<Long>();

    for(int i=0; i<nums.length;i++){
        //find the largest value smaller or equal to nums[i], return null if cannot find
        Long floor = set.floor((long) nums[i]);
        //find the smallest value larger to equal to nums[i], return null if cannot find
        Long ceil = set.ceiling((long) nums[i]);
        if((floor!=null && nums[i]-floor<=t)||(ceil!=null && ceil-nums[i]<=t)) {return true;}
        set.add((long) nums[i]);
        //keep a k size window
        //Example: k==3, when i==5, it can compare to nums[2,3,4],after checking i==5, remove nums[2]
        if (i>k-1) {
            set.remove((long) nums[i-k]);
        }
    }
    return false;

}

Reference

Leetcode TreeSet