Distribute Elements Into Two Arrays II - AVL Tree [JS]
Description Solution: AVL Tree Use an AVL tree to find the number of greater elements in O(log(n)) time complexity. Note: The AVL Tree is implemented from scratch since JS doesn't have a built-in self balancing BST. Time Complexity: O(n log(n)) Space Complexity: O(n) var resultArray = function(nums) { let n = nums.length, left = new AVLTree(), right = new AVLTree(); let arr1 = [nums[ 0 ]], arr2 = [nums[ 1 ]]; left.insert(nums[ 0 ]), right.insert(nums[ 1 ]); for (let i = 2 ; i < n; i++) { let greaterLeft = left.countGreater(nums[i]); let greaterRight = right.countGreater(nums[i]); if (greaterLeft > greaterRight) { left.insert(nums[i]); arr1.push(nums[i]); } else if (greaterRight > greaterLeft) { right.insert(nums[i]); arr2.push(nums[i]); } else { if (left.getSize() <= right.getSize()) { left.insert(nums[i]); arr1.push(nums[i]); } else { right.insert(n...