10ms non-cheating solution beats 98.84% submissions.


  • 5
    Y

    Unlike some solutions in the forum that convert int to long which is kinda of cheating, this solution doesn't convert.. Converting defeats the purpose of having max value test case (if the input contains max long itself, how to handle?)

    import java.util.Hashtable;
    
    public class Solution {
        public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    
    	if(k<=0||t<0||nums.length < 2) return false;
    		
            Hashtable<Integer,Integer> hs = new Hashtable<Integer,Integer>();
    
            if (t==0) {
                for (int i = 0; i<nums.length; i++){
                	if (i>k) {
                    	hs.remove(nums[i-k-1]);
                    }
                    if (hs.containsKey(nums[i])){
                        return true;
                    }
                    hs.put(nums[i],i);
                }
                return false;
            } else{
    
                for (int i = 0; i<nums.length; i++){
                	if (i>k) {
                    	// windowing, only preserve k#
                    	hs.remove(nums[i-k-1]/t);
                    }
                    if (hs.get(nums[i]/t) != null ){
                    	int delta = Math.abs(nums[i] - nums[hs.get(nums[i]/t)]);
                    	// The delta value could be larger than t, if one number is in (-t,0) and the other is in (0,t)
                    	if ( delta<=t) return true;
                    }
                    if (hs.get(nums[i]/t-1) != null ){
                    	int delta = nums[i] - nums[hs.get(nums[i]/t-1)];
                    	// If delta < 0, the distance between to numbers is larger than Integer.MAX_VALUE, which is larger than t.
                    	if ( delta<=t && delta >0) return true;
                    }
                    if (hs.get(nums[i]/t+1) != null ){
                    	int delta = nums[hs.get(nums[i]/t+1)] - nums[i];
                    	// If delta < 0, the distance between to numbers is larger than Integer.MAX_VALUE, which is larger than t.
                    	if ( delta<=t && delta >0) return true;
    
                    }
        
                    hs.put(nums[i]/t,i);
                }
                return false;
            }
        }
    }
    

  • 1
    Y

    Alternative for loop in if (t == 0)statement, without remove():

    for (int i = 0; i<nums.length; i++){
    	if (hs.get(nums[i]) != null && i - hs.get(nums[i]) <= k){
    		return true;
    	}
    	hs.put(nums[i],i);
    }
    return false;
    

  • 0
    D

    Thanks for sharing!


  • 2
    D

    The solution is incorrect: (-t, 0) and (0, t) share one bucket and therefore bring wrong overriding by hs.put().
    try [20,-4,4,-3],k=2,t=5
    expected answer is true; this solution returns false.


Log in to reply
 

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