BST & no TLE


  • 1
    J

    After digging into some other questions, I came back and found we can avoid
    worst case by construct the BST with the sorted arrays. Then we assign the geCount in update stage.

    class Solution {
        class TreeNode {
            int val;
            int geCount;
            TreeNode left;
            TreeNode right;
    
            TreeNode(int val) {
                this.val = val;
                geCount = 0; // NOTE
            }
        }
    
        int search(TreeNode root, long val) {
            if (root == null) return 0;
            if (root.val > val) {  // go left:[val, root.val>, and add root.geCount:[root.val, ..]
                return root.geCount + search(root.left, val);
            } else if (root.val == val) { // find the exact number
                return root.geCount;
            } else {
                return search(root.right, val);
            }
        }
        
        TreeNode construct(int[] nums, int left, int right) {
            if (left > right) return null;
            int m = left + (right - left) / 2;
            TreeNode root = new TreeNode(nums[m]);
            root.left = construct(nums, left, m - 1);
            root.right = construct(nums, m+1, right);
            return root;
        }
    
        TreeNode update(TreeNode root, int val) {
            if (root.val == val) {
                root.geCount++;
                return root;
            } else if (root.val < val) { // go right side;
                root.geCount++;
                update(root.right, val);
            } else {
                update(root.left, val);
            }
            return root;
        }
    
        public int reversePairs(int[] nums) {
            int count = 0;
            int[] cp_nums = Arrays.copyOf(nums, nums.length);
            Arrays.sort(cp_nums);
            TreeNode head = construct(cp_nums, 0, nums.length - 1);
    
            for (int num : nums) {                                    
                count += search(head, 2L * num + 1);            
                head = update(head, num);
            }
            return count;
        }
    }
    

  • 0
    D

    Quite smart and convenient solution! I just implemented the code based on your idea. Sorry for the repeating post made by me.


Log in to reply
 

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