LeetCode May 2020

CH4113N93-1337.js

// LeetCode May 2020

//1.js
/**
 * Definition for isBadVersion()
 * 
 * @param {integer} version number
 */

/**
 * @param {function} isBadVersion()
 * @return {function}
 */
var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
        let left = 0;
        let right = n;

        while(right >= left + 1) {
            let mid = Math.floor((right + left) / 2);

            if(isBadVersion(mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }

        }
        
        return right;
    };
};

// Time: O(log(n)) (assuming isBadVersion is O(1))
// Space: O(1)

// 2.js
/**
 * @param {string} J
 * @param {string} S
 * @return {number}
 */
var numJewelsInStones = function(J, S) {
    const distinct = new Set(J.split(''));
    let counter = 0;

    for(let letter of S) {
        if(distinct.has(letter)) {
            counter++;
        }
    }

    return counter;
}; 

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

// 3.js
/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function(ransomNote, magazine) {
    const letters = new Array(26).fill(0);

    for (let letter of magazine) {
        const code = letter.charCodeAt(0) - 97; // "a" charCode
        letters[code]++;
    }

    for (let letter of ransomNote) {
        const code = letter.charCodeAt(0) - 97; // "a" charCode
        if (!letters[code]) {
            return false;
        }
        letters[code]--;
    }

    return true;
}; 

// Time: O(n)
// Space: O(constant) = O(1)

// 4.js

/**
 * @param {number} num
 * @return {number}
 */
var findComplement = function(num) {
    const mask = (2 ** Math.ceil((Math.log2(num)))) - 1;
    return ~num & mask;
};

// Time: O(1)
// Space: O(1)

// 5.js https://leetcode.com/explore/featured/card/may-leetcoding-challenge/534/week-1-may-1st-may-7th/3320/
/**
 * @param {string} s
 * @return {number}
 */
var firstUniqChar = function(s) {
    const count = new Array(26).fill(0);
    const base = 'a'.charCodeAt(0);
    
    for(let i = 0; i < s.length; i++) {
        count[s.charCodeAt(i) - base]++;
    }
    
    for(let i = 0; i < s.length; i++) {
        const charCode = s.charCodeAt(i) - base;
        
        if(count[charCode] === 1) {
            return i;
        }
    }
    
    return -1;
};

// Time: O(n)
// Space: O(constant) = O(1)

// 6.js https://leetcode.com/explore/challenge/card/may-leetcoding-challenge/534/week-1-may-1st-may-7th/3321/
/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    const freqs = {};
    let maxNumber = null;
    let maxFreq = null;
    
    for(let i = 0; i < nums.length; i++) {
        const num = nums[i];
        freqs[num] = (freqs[num] || 0) + 1;
        
        if(freqs[num] > maxFreq) {
            maxNumber = num;
            maxFreq = freqs[num];    
        }
        
    }
    
    return maxNumber;
};

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

hermoso!

//7.js https://leetcode.com/explore/challenge/card/may-leetcoding-challenge/534/week-1-may-1st-may-7th/3322/
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} x
 * @param {number} y
 * @return {boolean}
 */
var isCousins = function(root, x, y) {
    const queue = [[root, 0, root.val]];
    
    let xDepth = null;
    let xParent = null;
    let yDepth = null;
    let yParent = null;

    
    while(queue.length && (!xDepth || !yDepth)) {
        const [node, depth, parent] = queue.shift();
        if (node.left) queue.push([node.left, depth + 1, node.val]);
        if (node.right) queue.push([node.right, depth + 1, node.val ]);
        
        if (node.val === x) {
            [xDepth, xParent] = [depth, parent];
        } else if (node.val === y) {
            [yDepth, yParent] = [depth, parent]
        }
    }

    return xDepth === yDepth && xParent !== yParent;
};

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

// 8.js https://leetcode.com/explore/featured/card/may-leetcoding-challenge/535/week-2-may-8th-may-14th/3323/
/**
 * @param {number[][]} coordinates
 * @return {boolean}
 */
var checkStraightLine = function(coordinates) {
    if(coordinates.lenght === 2) {
        return true;
    }
    
    const initialSlope = Math.abs((coordinates[1][0] - coordinates[0][0]) / (coordinates[1][1] - coordinates[0][1]));
    
    for (let i = 2; i < coordinates.length; i++) {
        const [x1, x2] = coordinates[i -1]
        const [y1, y2] = coordinates[i]
        const slope = Math.abs((y1 - x1) / (y2 - x2))
        
        if (initialSlope !== slope) {
            return false
        }
    }
    
    return true
};

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

// 9.js https://leetcode.com/explore/challenge/card/may-leetcoding-challenge/535/week-2-may-8th-may-14th/3324/
/**
 * @param {number} num
 * @return {boolean}
 */
var isPerfectSquare = function(num) {
    for(let i = 1; i <= num; i++) {
        let curr = i ** 2
        if(curr === num) {
            return true
        } else if(curr > num) {
            return false
        }
    }
    
    return false
};

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

// 10.js https://leetcode.com/explore/featured/card/may-leetcoding-challenge/535/week-2-may-8th-may-14th/3325/
/**
 * @param {number} N
 * @param {number[][]} trust
 * @return {number}
 */
var findJudge = function(N, trusts) {
    const trusteeAdjacency = new Array(N + 1).fill(0);
    const trusterAdjacency = new Array(N + 1).fill(0);
    
    for(let [truster, trustee] of trusts) {        
        trusteeAdjacency[trustee] = trusteeAdjacency[trustee] + 1;
        trusterAdjacency[truster] = trusterAdjacency[truster] + 1;
    }
    
    for(let trustee = 1; trustee < trusteeAdjacency.length; trustee++) {
        if ((trusteeAdjacency[trustee] + 1) === N && trusterAdjacency[trustee] === 0) {
            return trustee;
        }
    }
            
    return -1;
};

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

// 11.js https://leetcode.com/explore/featured/card/may-leetcoding-challenge/535/week-2-may-8th-may-14th/3326/

/**
 * @param {number[][]} image
 * @param {number} sr
 * @param {number} sc
 * @param {number} newColor
 * @return {number[][]}
 */

const fill = (image, y, x, newColor, startingColor) => {
    if (y < 0 || y >= image.length || x < 0 || x > image[y].length) {
        return;
    }
    
    if (image[y][x] === startingColor && image[y][x] !== newColor) {
        image[y][x] = newColor;
        floodFill(image, y, x, newColor, startingColor)
    }
}

var floodFill = function(image, y, x, newColor, startingColor = image[y][x]) {
    image[y][x] = newColor;
    fill(image, y - 1, x, newColor, startingColor);
    fill(image, y + 1, x, newColor, startingColor);
    fill(image, y, x - 1, newColor, startingColor);
    fill(image, y, x + 1, newColor, startingColor);
        
    return image;
};
// Time: O(n) 
// Space: O(n)

// 12.js https://leetcode.com/explore/challenge/card/may-leetcoding-challenge/535/week-2-may-8th-may-14th/3327/
/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNonDuplicate = function(nums) {
    let [l, r] = [0, nums.length - 1]
    
    while(r >= l) {
        const mid = Math.floor((r + l) / 2)
        if (nums[mid] !== nums[mid + 1] && nums[mid] !== nums[mid - 1]) {
            return nums[mid]
        }
		
		const compareTo = mid % 2 === 0 ? nums[mid + 1]: nums[mid - 1]
        
        if (compareTo === nums[mid]) {
            l = mid + 1
        } else {
            r = mid
        }
    }
};

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

// 13.js
/**
 * @param {string} num
 * @param {number} k
 * @return {string}
 */
var removeKdigits = function(num, k) {
    let answer = num
    
    for(let times = 0; times < k; times++) {
        let wasSet = false
        
        for(let i = 0; i < answer.length - 1; i++) {
            if (answer[i] > answer[i+1]) {
                answer =  answer.slice(0, i) + answer.slice(i + 1)
                wasSet = true
                break
            }
        }
        
        if(!wasSet) {
            answer = answer.slice(0, -1)   
        }
    }
    
    const indexOfNonZero = answer.search(/[1-9]/)
    
    return indexOfNonZero === -1 ? "0" : answer.slice(indexOfNonZero)
};

// Time: O(n)
// Space: O(n) //can be done in-place, didn't want to destroy the input

// 14.js
class Node {
    constructor(val) {
        this.children = new Map()
        this.isFinalWord = false
    }
}

class Trie {
    constructor() {
        this.root = new Node('*')
    }
    
    insert = (word) => {
        let node = this.root
        let index = 0
        
        while (node.children.get(word[index]) && index < word.length) {
            node = node.children.get(word[index])
            index++
        }
        
        while (word.length > index) {
            const currentNode = new Node()
            node.children.set(word[index], currentNode)
            node = currentNode
            index++
        }
        
        node.isFinalWord = true
    };

    search = (word) => {
        let node = this.root
        
        for (let letter of word) {
            node = node.children.get(letter)
            
            if (!node) {
                return false
            }
        }
        
        return node.isFinalWord
    };

    startsWith = (prefix) => {
        let node = this.root
        
        for (let letter of prefix) {
            node = node.children.get(letter)
            
            if (!node) {
                return false
            }
        }
        
        return true
    };
}

// Time: O(n) (where n is word.length)
// Space: O(n)

//15.js 
/**
 * @param {number[]} A
 * @return {number}
 */

const maxKadane = (arr) => {
  let max = 0
  let maxSoFar = 0
  
    for (let i = 0; i < arr.length; i++) {
      maxSoFar = Math.max(maxSoFar + arr[i], 0)
      max = Math.max(max, maxSoFar)
    }
  
  return max
}

var maxSubarraySumCircular = function (A) {
  // First, get the max subarray sum
  const maxSingle = maxKadane(A)
  
  // If it returned 0 it means that all numbers are negative, just return the max out of them
  if (maxSingle === 0) {
    return Math.max(...A)
  } 
  
  const maxNegated = maxKadane(A.map(e => e * -1))
  const sum = A.reduce((acc, cur) => acc += cur) 
  
  return Math.max(maxSingle, sum + maxNegated)
};


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

// 16.js
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var oddEvenList = function(head) {
  if(!head) return null
  let [node, nextEven, evens] = [head, head.next, head.next]
  
  while(nextEven !== null && nextEven.next !== null) {
    node.next = node.next.next
    node = node.next
    nextEven.next = node.next
    nextEven = nextEven.next
  }
  
  node.next = evens
  
  return head
};

// Time: O(n)
// Space: O(1) (I'm just saving the references for the even nodes)

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