Java treeset implementation NlogK

  • 13

    this is a very good demonstration of the use of TreeSet ---- which we rarely use normally.

        public class Solution {
        public boolean containsNearbyAlmostDuplicate(final int[] nums, int kk, long t) {
            if (nums.length < 2) return false;
            if (kk == 0) return false;
            TreeSet<Long> window = new TreeSet<Long>();
            for(int i=0;i<nums.length;i++) {
                // check dup, window size <= kk right now
            	if ( window.floor(nums[i] + t) !=null && window.floor(nums[i]+t) >= nums[i]-t ) return true;
                window.add(new Long(nums[i]));
                if (i >= kk) {
                    //remove one, the size has to be kk on the next fresh step
                	window.remove(new Long(nums[i-kk]));
            return false;

  • 0

    why TreeSet<Integer> doesn't have the floor() method?

  • 0

    Could you please tell me why it's faster when treeset's elements are Long instead of Integer?

  • 1

    I don't think it has to do with performance. It's possible that nums[i] + t > Integer.MAX_VALUE.
    Nice solution!

  • 0

    How is this nlogk? Isnt this supposed to be nlogn which is the cost of constructing the tree set?

  • 1

    nlogk since his treeSet's size is k

  • 0

    @liji94188 you need to declare it in this way :
    TreeSet<Integer> set = new TreeSet<>();

Log in to reply

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