10-liner Java solution using TreeSet


  • 0

    Re: Java O(N lg K) solution

    Learned floor/ceiling from your solution! At first I use subSet() which is obviously much slower and handle duplicate case explicitly.

        public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
            if (nums.length == 0 || k <= 0 || t < 0) return false;
            TreeSet<Integer> tree = new TreeSet<>();
            for (int i = 0; i < nums.length; i++) {
                if (tree.size() >= k + 1)
                    tree.remove(nums[i - k - 1]);
                if (!tree.add(nums[i]))  // Find duplicate in +/-k range
                    return true;
                                                                   
                int low = (nums[i] > Integer.MIN_VALUE + t) ? nums[i] - t : Integer.MIN_VALUE;
                int high = (nums[i] < Integer.MAX_VALUE - t) ? nums[i] + t : Integer.MAX_VALUE;
                if (tree.subSet(low, true, high, true).size() > 1)
                    return true;
            }
            return false;
        }
    

    Inspired by yours, compare nums[i] with previous K elements in Set ahead, so the duplicate case is handled implicitly. Here is my final solution which is more efficient and elegant. Thanks for your sharing!

        public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
            if (nums.length == 0 || k <= 0 || t < 0) return false;
            TreeSet<Long> tree = new TreeSet<>();
            for (int i = 0; i < nums.length; i++) {
                Long ceil = tree.ceiling((long) nums[i] - t);   // least num that >= num-t
                Long floor = tree.floor((long) nums[i] + t);    // greatest num that <= num+t
                if ((floor != null && floor >= nums[i]) || (ceil != null && ceil <= nums[i]))
                    return true;
                if (tree.add((long) nums[i]) && i >= k)         // tree has K+1, remove one to keep K
                    tree.remove((long) nums[i - k]);
            }
            return false;
        }
    

Log in to reply
 

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