Java O(N lg K) solution


  • 142
    J

    This problem requires to maintain a window of size k of the previous values that can be queried for value ranges. The best data structure to do that is Binary Search Tree. As a result maintaining the tree of size k will result in time complexity O(N lg K). In order to check if there exists any value of range abs(nums[i] - nums[j]) to simple queries can be executed both of time complexity O(lg K)

    Here is the whole solution using TreeMap.


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

  • 2
    M

    Good use of TreeSet


  • 0
    M
    This post is deleted!

  • 3
    J

    Apparently the task is to find duplicates, so it not suppose to reach the situation that you have more then one occurrence of the given value in the tree map. Although if you can provide an example input that illustrates this situation I would be grateful.


  • 0
    M

    I agree, thank you.


  • 0
    S

    why do you set floor and ceiling final? they will change in next loop anyway.


  • 18
    J

    Although you passed the test cases. There's one issue there: overflow.
    let's say nums[ind] is Integer.MAX_VALUE, t is 20. You cannot just do nums[ind] + t.


  • 0
    J

    Quite right, although the only solution that comes to my mind to solve this is only to expand the data type size from 32 bit integer to 64 bit long.


  • 0
    B

    That would not be a problem. Ceiling has already handled it.


  • 0
    Y

    I think the judgement statement in the if brackets should be floor >= nums[ind] - t , ceil <= nums[ind] + t; However, it will overflow,and cannot pass all the test cases, and I think use bigger data type can solve this problem!


  • 1
    3

    Concise and Genius! Good use of TreeSet property!!!


  • 8
    J

    great solution. Have to cast to long to get it pass all test cases.(Integer overflow)

    	public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    	if (nums.length < 2 || k == 0) {
    		return false;
    	}
    	TreeSet<Long> set = new TreeSet<>();
    
    	int i = 0;
    	while (i < nums.length) {
    		Long floor = set.floor((long) nums[i]);
    		Long ceiling = set.ceiling((long) nums[i]);
    		if ((floor != null && nums[i] - floor <= t ) ||
    				(ceiling != null && ceiling - nums[i] <= t)) {
    			return true;
    		}
    		set.add((long) nums[i++]);
    		if (i > k) {
    			set.remove((long) nums[i - k - 1]);
    		}
    	}
    	return false;
    }

  • 0

    What an elegant solution! Thank you for sharing!


  • 0
    F

    Brilliant Idea.


  • 0
    W

    i has a little question that why we start removing when ind == k,i mean at that time the least ind is 0,and the greatest is k,the difference is k.it still satisfy the rule.
    I think we should hold a window which size is k+1.
    Am i wrong.
    the problem said "the difference between i and j is at most k.".


  • 0
    K

    how about save one ceiling operation

    public class Solution {
        public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
            if (nums == null || nums.length == 0 || k <= 0) {
                return false;
            }
    
            final TreeSet<Long> values = new TreeSet<>();
            for (int ind = 0; ind < nums.length; ind++) {
    
                Long floor = values.floor((long)nums[ind] + t);
                if (floor != null && floor + t >= nums[ind]) {
                    return true;
                }
    
                values.add((long)nums[ind]);
                if (ind >= k) {
                    values.remove((long)nums[ind - k]);
                }
            }
    
            return false;
        }
    }

  • 7
    Y

    hi, @jmnarloch , brilliant solution ! I was originally worried about duplicates in the TreeSet and the validity of add and remove. Then I realized that if there were duplicates within k, we would have returned true already. Great implicit logic!


  • 0
    Y

    Hi @kennethliaoke , what is the intuition of dropping the ceiling ? from your floor computation, i know that:

    floor <= nums[ind] + t, so

    floor + t <= nums[ind] + t + t,

    yet so what ? could you explain that ? Thanks!


  • 0
    K

    because if floor <= nums[ind] + t and floor >= nums[ind] - t, then that's a duplicate. If floor < nums[ind] - t, there won't be a duplicate because floor is the biggest value in the treeset that is less than (nums[ind] + t). Hope it helps.


  • 0
    Y

    How would ceiling handle it?


Log in to reply
 

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