LeetCode May 2020

CH4113N93-1337.js

// LeetCode May 2020

// 20.js

var kthSmallest = function (root, k) {
  let stack = [root];
  let node = root;

  while (stack.length) {
    while (node) {
      stack.push(node);
      node = node.left;
    }
    node = stack.pop();

    if (k === 1) {
      return node.val;
    } else {
      k--;
    }

    node = node.right;
  }

  return null;
};

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

// 21.js
/**
 * @param {number[][]} matrix
 * @return {number}
 */
const isValidSubMatrix = (matrix, x, y, side) => {
  if (y + side > matrix.length || x + side > matrix[y].length) {
    return false;
  }

  if (side === 1) {
    return matrix[y][x] === 1;
  }

  for (let sy = y; sy < y + side; sy++) {
    for (let sx = x; sx < x + side; sx++) {
      if (!matrix[sy][sx]) {
        return false;
      }
    }
  }

  return true;
};

var countSquares = function (matrix) {
  const times = Math.min(matrix.length, matrix[0].length);
  let number = 0;

  for (let side = 1; side <= times; side++) {
    for (let y = 0; y < matrix.length; y++) {
      for (let x = 0; x < matrix[y].length; x++) {
        if (isValidSubMatrix(matrix, x, y, side)) {
          number++;
        }
      }
    }
  }

  return number;
};

// Time: O(n ^ 3) or O(n ^ 4), lol
// Space: O(1)

// 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)