220. 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 absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

Extension of previous 217 and 219 

Solution

This problem is an extension problem of previous two problems. 

However it is much more difficult than previous two.

Algorithm we used here is bucket mapping.

The bucket size I am using is t, and ..[-t-1, -1],[0,t],[t+1,2t+1]..

for example, let's set t=3, then the bucket we have are ...[-8,-5], [-4,-1], [0, 3], [4,7]...

The corresponding index is -2,-1,0,1 if we define our index= (nums[i]>=0) ? nums[i]/(t+1) : (nums[i]-t)/(t+1)

If for a given range of k, we find a same bucket index which means we find two distinct indices such that the absolute difference is at most t because they are in the same bucket. Also we check if map contains bucket of index-1 and index+1, if it contains, we check if they meet the statement that the absolute difference is at most t. The essential iteration invariant of here is for a given range of k, all bucket index should be unique, otherwise we will return true during the first check. Also, we need to remove bucket index when the element is out of range k for next num element. 

   public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {  
     if(t<0) return false;  
     long div=(long)t+1;  
     HashMap<Long,Integer> map=new HashMap<Long,Integer>();  
     for(int i=0;i<nums.length;i++){  
       long bucket=(nums[i]>=0)? (long)nums[i]/div : ((long)nums[i]-t)/div;  
       if(map.containsKey(bucket)) return true;  
       if(map.containsKey(bucket-1)){  
         int num=map.get(bucket-1);  
         long diff=(long)nums[i]-(long)num;  
         if(diff<=t) return true;  
       }  
       if(map.containsKey(bucket+1)){  
         int num=map.get(bucket+1);  
         long diff=(long)num-(long)nums[i];  
         if(diff<=t) return true;  
       }  
       map.put(bucket,nums[i]);  
       if(i>=k){  
         long preBucket=(nums[i-k]>=0)? (long)nums[i-k]/div : ((long)nums[i-k]-t)/div;  
         map.remove(preBucket);  
       }  
     }  
     return false;      
   }