LeetCode May 2020

CH4113N93-1337.js

// LeetCode May 2020

// 22.js
/**
 * @param {string} s
 * @return {string}
 */
var frequencySort = function(s) {
  // It would be nice if we had some type of ordered Map
  // to prevent the sort in line 15
  const freq = {}
  
  for (let letter of s) {
    freq[letter] = (freq[letter] || 0) + 1
  }
  
  return Object.entries(freq)
    .sort((a, b) => b[1] - a[1])
    .map(e => e[0].repeat(e[1]))
    .join('')
};

// Time: O(n)
// Space: O(n)

// 23.js
/**
 * @param {number[][]} A
 * @param {number[][]} B
 * @return {number[][]}
 */
var intervalIntersection = function(A, B) {
  const getIntersection = (a, b) => {
    if (a[1] < b[0] || a[0] > b[1]) 
      return null
    
    return [Math.max(a[0], b[0]), Math.min(a[1], b[1])]
  }
  
  let pivotA = 0
  let pivotB = 0
  const answer = []
  
  while (pivotA < A.length && pivotB < B.length) {
    const intersection = getIntersection(A[pivotA], B[pivotB])
    if(intersection) {
      answer.push(intersection)
    }
    
    if(A[pivotA][1] < B[pivotB][1]) {
      pivotA++
    } else {
      pivotB++
    }  
  }
  
  return answer
};

// Time: O(A + B) = O(n)
// Space: O(N)

// 24.js
const getLast = (arr, level = 1) => (arr.length ? arr[arr.length - level] : null);
const bstFromPreorder = function (preorder) {
  if (!preorder.length) {
    return null;
  }

  const leaves = [[new TreeNode(preorder.shift()), -Infinity, Infinity]];

  while (preorder.length) {
    const currentVal = preorder.shift();

    while (currentVal > getLast(leaves)[2] || currentVal < getLast(leaves)[1]) {
      leaves.pop();
    }

    const [leave, min, max] = getLast(leaves);

    if (currentVal > leave.val) {
      leave.right = new TreeNode(currentVal);
      leaves.push([leave.right, leave.val, max]);
    } else if (currentVal < leave.val) {
      leave.left = new TreeNode(currentVal);
      leaves.push([leave.left, min, leave.val]);
    }
  }

  return leaves[0][0];
};

// Time: O(n)
// Space: O(n)