O(N * K) solution (9ms, beats ~99%)


  • 0
    J

    This is is similar to the solution using TreeSet. Loop through the array, maintaining a BST of the k previous values. You know the answer, if it exists, must be in this tree, so you use the tree to see if there's a value in there that satisfies the t criterion.

    A key speedup over the given TreeSet solution is that you can determine whether or not the "near duplicate" criterion is satisfied while inserting into the tree, so you don't have to check the ceiling/floor after insertion. If at any point during the insertion process of the value we have |current value - value in the tree| <= k, we return true. Unfortunately, if we do this, we can't use the nice TreeSet structure provided to us by Java, so I had to write stuff manually. The BST is also not self-balancing, so it's not accurate to say it's O(N lg K).

    public class Solution {
        public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
            if (nums == null || nums.length <= 1 || k <= 0 || t < 0) {
                return false;
            }
    
            k = Math.min(nums.length - 1, k);
            TreeNode root = new TreeNode(nums[0]);
            for (int j = 1; j < nums.length; j++) {
                if (j > k) {
                    root = deleteNode(root, nums[j - k - 1]);
                }
                if (root.insertWithAlmostDuplicateCheck(nums[j], t)) {
                    return true;
                }
            }
            return false;
        }
        
        class TreeNode {
            int val;
            TreeNode left, right;
            
            TreeNode(int val) {
                this.val = val;
            }
            
            boolean insertWithAlmostDuplicateCheck(int valToInsert, int t) {
                long diff = (long) (valToInsert) - (long) (val);
                if ((diff >= 0 ? diff : -diff) <= t) {
                    return true;
                }
    
                if (diff < 0) {
                    if (left == null) {
                        left = new TreeNode(valToInsert);
                        return false;
                    } else {
                        return left.insertWithAlmostDuplicateCheck(valToInsert, t);
                    }
                } else {
                    if (right == null) {
                        right = new TreeNode(valToInsert);
                        return false;
                    } else {
                        return right.insertWithAlmostDuplicateCheck(valToInsert, t);
                    }
                }
            }
        }
        
        // ------------- standard, unimportant stuff below ------------- //
        private TreeNode deleteNode(TreeNode root, int value) {
            if (root == null)
                return null;
            if (root.val > value) {
                root.left = deleteNode(root.left, value);
            } else if (root.val < value) {
                root.right = deleteNode(root.right, value);
            } else {
                if (root.left != null && root.right != null) {
                    TreeNode temp = root;
                    TreeNode minNodeForRight = minimumElement(temp.right);
                    root.val = minNodeForRight.val;
                    deleteNode(root.right, minNodeForRight.val);
                } else if (root.left != null) {
                    root = root.left;
                } else if (root.right != null) {
                    root = root.right;
                } else {
                    root = null;
                }
            }
            return root;
        }
        
        private TreeNode minimumElement(TreeNode root) {
            if (root.left == null) {
                return root;
            } else {
                return minimumElement(root.left);
            }
        }
    }
    

Log in to reply
 

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