LeetCode May 2020

CH4113N93-1337.js

// LeetCode May 2020

// 17.js

const getCode = (s, i) => s.charCodeAt(i) - 'a'.charCodeAt(0);

const areEqualArrays = (a1, a2) => {
  for (let i = 0; i <= a1.length; i++) {
    if (a1[i] !== a2[i]) {
      return false;
    }
  }
  return true;
};

const findAnagrams = (p, s) => {
  const freqS = new Array(26).fill(0);
  const freqP = new Array(26).fill(0);

  const answer = [];

  for (let i = 0; i < s.length; i++) {
    freqS[getCode(s, i)]++;
  }

  for (let i = 0; i < s.length; i++) {
    freqP[getCode(p, i)]++;
  }

  for (let i = s.length; i < p.length; i++) {
    if (areEqualArrays(freqS, freqP)) {
      answer.push(i - s.length);
    }

    freqP[getCode(p, i)]++;
    freqP[getCode(p, i - s.length)]--;
  }
  
  if (areEqualArrays(freqS, freqP)) {
    answer.push(p.length - s.length);
  }

  return answer;
};

// Time: O(S + P) = O(n)
// Space: O(1)

// 18.js
var checkInclusion = function (s1, s2) {
  if (s1.length > s2.length) {
    return false;
  }

  const freq = new Array(26).fill(0);
  const base = 'a'.charCodeAt(0);
  const getCode = (s, i) => s.charCodeAt(i) - base;

  const areEqualArrays = (a1, a2) => {
    for (let i = 0; i <= a1.length; i++) {
      if (a1[i] !== a2[i]) {
        return false;
      }
    }
    return true;
  };

  for (let i = 0; i < s1.length; i++) {
    freq[getCode(s1, i)]++;
  }

  for (let i = 0; i < s2.length; i++) {
    if (freq[getCode(s2, i)] > 0) {
      const currentFreq = new Array(26).fill(0);

      for (let j = i; j < s2.length; j++) {
        const currentCode = getCode(s2, j);
        currentFreq[currentCode]++;
        // if we find another character before length, just discard the positions
        if (freq[currentCode] === 0) {
          i = j;
          break;
        }

        if (j - i < s1.length - 1) {
          continue;
        }

        if (areEqualArrays(freq, currentFreq)) {
          return true;
        } else {
          currentFreq[getCode(s2, j - s1.length + 1)]--;
        }
      }
    }
  }

  return false;
};

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

// 19.js
class StockSpanner {
  max = -Infinity;
  maxCount = 0;
  localMax = [];

  next(stock) {
    const peek = (arr) => arr[arr.length - 1];

    if (stock >= this.max) {
      this.max = stock;
      const localMax = this.localMax.length
        ? this.localMax.reduce((acc, cur) => (acc += cur[1]), 0)
        : 0;
      this.maxCount = this.maxCount + localMax + 1;
      this.localMax = [];
      return this.maxCount;
    }

    let localCount = 1;

    while (this.localMax.length && stock >= peek(this.localMax)[0]) {
      const [_, count] = this.localMax.pop();
      localCount += count;
    }

    this.localMax.push([stock, localCount]);

    return localCount;
  }
}

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

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