Distribute Elements Into Two Arrays II - AVL Tree [JS]

By on

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(nums[i]);
        arr2.push(nums[i]);
      }
    }
  }
  return [...arr1, ...arr2];
};

class AVLTreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
    this.height = 1;
    this.size = 1; // number of nodes in tree rooted at this node
  }
}

class AVLTree {
  constructor() {
    this.root = null;
  }
  search(val, node = this.root) {
    if (!node) return null;
    if (node.val === val) return node;
    if (val < node.val) {
      return this.search(val, node.left);
    } else {
      return this.search(val, node.right);
    }
  }
  insert(val) {
    return this.root = this._insert(val, this.root);
  }
  _insert(val, node) {
    if (!node) return new AVLTreeNode(val);
    if (val < node.val) {
      node.left = this._insert(val, node.left);
    } else {
      node.right = this._insert(val, node.right);
    }
    node.height = 1 + Math.max(this._getHeight(node.left), this._getHeight(node.right));
    node.size = 1 + this.getSize(node.left) + this.getSize(node.right);

    return this._rebalance(node);
  }
  remove(val, node = this.root) {
    // To ensure we don't delete all occurances of `val`, pass in the reference of one occurance.
    // To delete all nodes with value `val`, remove the check for `nodeToRemove` in _remove.
    const nodeToRemove = this.search(val, node);
    return this.root = this._remove(val, nodeToRemove, node);
  }
  // Four scenarios for deletion:
    // 1. node to delete has no children - just delete it
    // 2. node to delete only has a left child - replace it with the left child
    // 3. node to delete only has a right child - replace it with the right child
    // 4. node to delete has both left and right children - replace it with the next smallest node that is larger (use in order traversal to find the leftmost node in the right child)
  _remove(val, nodeToRemove, node) {
    if (!node) return null;
    if (val < node.val) {
      node.left = this._remove(val, nodeToRemove, node.left);
    } else if (val > node.val) {
      node.right = this._remove(val, nodeToRemove, node.right);
    } else if (val === node.val && node === nodeToRemove) {
      if (!node.left && !node.right) return null;
      if (!node.right) return node.left;
      if (!node.left) return node.right;

      // has both left and right children
      // inorder traversal on the right child to get the leftmost node
      // replace the node value with the leftmost node value and remove the leftmost node from the right subtree
      const leftmostNode = this._getLeftmost(node.right);
      node.val = leftmostNode.val;

      node.right = this._remove(leftmostNode.val, this.search(leftmostNode.val, node.right), node.right);
    } else {
      return node;
    }
    node.height = 1 + Math.max(this._getHeight(node.left), this._getHeight(node.right));
    node.size = 1 + this.getSize(node.left) + this.getSize(node.right);

    return this._rebalance(node);
  }
  countGreater(val, node = this.root) {
    if (!node) return 0;

    if (node.val > val) {
      return 1 + this.getSize(node.right) + this.countGreater(val, node.left);
    } else {
      return this.countGreater(val, node.right);
    }
  }
  _getLeftmost(node) {
    while (node.left) {
      node = node.left;
    }
    return node;
  }
  _getHeight(node = this.root) {
    return node ? node.height : 0;
  }
  getSize(node = this.root) {
    return node ? node.size : 0;
  }
  _getBalance(node = this.root) {
    return node ? this._getHeight(node.left) - this._getHeight(node.right) : 0;
  }
  _leftRotation(node) { 
    let rightNode = node.right;
    let rightNodeLeftChild = rightNode.left;
    rightNode.left = node;
    node.right = rightNodeLeftChild;

    // node is now below rightNode and needs to be updated first
    node.height = 1 + Math.max(this._getHeight(node.left), this._getHeight(node.right));
    rightNode.height = 1 + Math.max(this._getHeight(rightNode.left), this._getHeight(rightNode.right));

    node.size = 1 + this.getSize(node.left) + this.getSize(node.right);
    rightNode.size = 1 + this.getSize(rightNode.left) + this.getSize(rightNode.right);

    return rightNode; // right node is the new root
  }
  _rightRotation(node) {
    let leftNode = node.left;
    let leftNodeRightChild = leftNode.right;
    leftNode.right = node;
    node.left = leftNodeRightChild;

    // node is now below leftNode and needs to be updated first
    node.height = 1 + Math.max(this._getHeight(node.left), this._getHeight(node.right));
    leftNode.height = 1 + Math.max(this._getHeight(leftNode.left), this._getHeight(leftNode.right));

    node.size = 1 + this.getSize(node.left) + this.getSize(node.right);
    leftNode.size = 1 + this.getSize(leftNode.left) + this.getSize(leftNode.right);

    return leftNode; // left node is the new root
  }
  _rebalance(node) {
    const balance = this._getBalance(node);
    if (balance > 1 && this._getBalance(node.left) >= 0) { // left left
      return this._rightRotation(node);
    } else if (balance > 1 && this._getBalance(node.left) < 0) { // left right
      node.left = this._leftRotation(node.left);
      return this._rightRotation(node);
    } else if (balance < -1 && this._getBalance(node.right) <= 0) { // right right
      return this._leftRotation(node);
    } else if (balance < -1 && this._getBalance(node.right) > 0) { // right left
      node.right = this._rightRotation(node.right);
      return this._leftRotation(node);
    }
    return node;
  }
}
Location: Auckland, New Zealand

Comments

Post a Comment

Popular posts from this blog

Maximum Value of an Ordered Triplet II - Two Solutions [JS]

By on
Description   Solution 1: Prefix Max Summary: Anchor at  nums[j] . We want  nums[i]  and  nums[k]  to be as larger as possible, and  nums[j]  to be as small as possible to ensure the maximum value. Calculate the maximum value on the right of each index  i :  maxRight[i]  = maximum value from index  i  to  n - 1 Go through  nums  from left to right and take each element as  nums[j] . Keep track of the maximum value on the left. Get the maximum value on the left and right of  nums[j] . Record the maximum value. Time Complexity:  O(n) Space Complexity:  O(n) var maximumTripletValue = function ( nums ) { let n = nums.length, maxRight = [...nums]; for ( let i = n - 2 ; i >= 0 ; i--) { maxRight[i] = Math .max(nums[i], maxRight[i + 1 ]); } let maxLeft = 0 , ans = 0 ; for ( let j = 0 ; j < n; j++) { if (j > 0 && j < n - 1 ) { ans = Math .max(an...
Read more

Maximum Sum of Distinct Subarrays With Length K - Sliding Window w/ Two Pointers & Set [JS]

By on
Description  Solution: Sliding Window w/ Two Pointers & Set Maintain a sliding window of unique numbers with maximum size of  k . We can store the numbers in the window in a hashset. When we move the right pointer up, move the left pointer up until: all numbers in the window are unique the window size  <= k Time Complexity:  O(n)  246ms Space Complexity:  O(k)  71.5MB var maximumSubarraySum = function ( nums, k ) { let set = new Set (), sum = 0 ; let ans = 0 , n = nums.length; for ( let j = 0 , i = 0 ; j < n; j++) { sum += nums[j]; while (set.has(nums[j]) || j - i >= k) { sum -= nums[i]; set.delete(nums[i]); i++; } set.add(nums[j]); if (j - i + 1 === k) ans = Math .max(ans, sum); } return ans; };
Read more

Sum of Prefix Scores of Strings - Trie [JS]

By on
Description   Solution: Trie Store each word in a trie. For every node in the trie, keep track of the number of words it is part of. Since we stored the count of words on every node, we can calculate the count of every prefix for every word on the fly. n = number of words ,  m = max(words[i].length) Time Complexity:  O(nm) Space Complexity:  O(26^m)  at worst var sumPrefixScores = function ( words ) { let trie = new Trie(); for ( let word of words) { trie.add(word); } let n = words.length, res = Array (n); for ( let i = 0 ; i < words.length; i++) { res[i] = trie.getScore(words[i]); } return res; }; class TrieNode { constructor ( ) { this .children = {}; this .count = 0 ; } } class Trie { constructor ( ) { this .root = new TrieNode(); } add ( word ) { let node = this .root; for ( let i = 0 ; i < word.length; i++) { node = node.children; let char = word[i]; if (...
Read more

Maximum Count of Positive Integer and Negative Integer - Binary Search [JS]

By on
Description  Solution: Binary Search Since  nums  is sorted, we can use binary search: Binary search for the index of the rightmost negative number. Binary search for the index of the leftmost positive number. Based on the indexes we can find the amount of negative and positive numbers. Time Complexity:  O(log(n))  64ms Space Complexity:  O(1)  43.7MB var maximumCount = function ( nums ) { return Math .max(upper_bound(nums), lower_bound(nums)); }; // binary search for the rightmost negative number function upper_bound ( nums ) { let low = 0 , high = nums.length - 1 ; while (low < high) { let mid = Math .ceil((low + high) / 2 ); if (nums[mid] < 0 ) low = mid; else high = mid - 1 ; } return nums[ 0 ] >= 0 ? 0 : low + 1 ; } // binary search for the leftmost positive number function lower_bound ( nums ) { let low = 0 , high = nums.length - 1 ; while (low < high) { let mid = Math .floor((low + hi...
Read more

Count Subarrays With Median K - Count Left & Right Balance [JS]

By on
Description   Solution: Count Left & Right Balance For a subarray to have median of  k : The subarray must contain  k . k  must be the middle element (if odd) or lower mid element (if even). Create subarrays revolving around  nums[i] = k . How do we find whether  k  is the mid/lower mid element? Starting from  k , count the "balance" on the left and right of  k . If  nums[i] < k , add  -1  to the balance. If  nums[i] > k , add  1  to the balance. If  k  is the mid element, the left balance + right balance =  0 . If  k  is the lower mid element, left balance + right balance =  1 . Store the count of left balances in a hashmap. Go through each right balance, Balance = 0 : Count the number of left balances that are equal to ( -right balance ) Balance = 1 : Count the number of left balances that are equal to ( -right balance + 1 ) Time Complexity:  O(n) Space Complexity:...
Read more