Same as most popular AC using buckets but with a few comments that may be helpful


  • 1
    J
     public class Solution {
        
        // for the negative case the, - 1, for example ensures negative values with magnitude less then t dont map to 
        // zero where positive ones with same magnitude will also map to zero
    	long getIdx(long v, long t){
    		if(v < 0) return v/t - 1; 
    		else return v/t;
    	}
    	
    	public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    		if(t < 0) return false;
    		else if(k <= 0) return false;
    		
    		long m = ((long) t + 1); // use t+1 for case when t = 0 for example
    		Map<Long, Long> buckets = new HashMap<>();
    		for(int i=0; i<nums.length; i++){
    			long b = getIdx(nums[i], m);
    			
    			if(buckets.containsKey(b)) return true;
    			else if(buckets.containsKey(b-1) && Math.abs(nums[i] - buckets.get(b-1)) <= t) return true;
    			else if(buckets.containsKey(b+1) && Math.abs(nums[i] - buckets.get(b+1)) <= t) return true;
    			
    			// Note - we are never loosing information here because if there was anything already in bucket b then
    			// we would have a hit and have returned true already
    			buckets.put(b, ((long) nums[i]));
    			if(i >= k) buckets.remove(getIdx(nums[i-k], m));
    		}
    		return false;
    	}
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.