Skip to main content

7 posts tagged with "leetcode"

View All Tags

15. 3Sum

· 2 min read
Shi Xinyu
Shi Xinyu
Front End Developer

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example

Example 1:

Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] Explanation: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0. The distinct triplets are [-1,0,1] and [-1,-1,2]. Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1] Output: [] Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0] Output: [[0,0,0]] Explanation: The only possible triplet sums up to 0.

/**
 * @param {number[][]} matrix
 * @return {number[][]}
 */
function threeSum(input: number[]) {
  const length = input.length;
  input.sort((a, b) => a - b);
  const res = new Set<string>();

  function checkPosition(mid: number) {
    let left = mid - 1;
    let right = mid + 1;

    while (left >= 0 && right < length) {
      const sum = input[left] + input[mid] + input[right];
      if (sum === 0) {
        res.add([input[left], input[mid], input[right]].join(","));
        left--;
      }
      if (sum < 0) {
        right++;
      }
      if (sum > 0) {
        left--;
      }
    }
  }

  for (let i = 1; i < length - 1; i++) {
    checkPosition(i);
  }
  return [...res].map((v) => v.split(","));
}

16

· One min read
Shi Xinyu
Shi Xinyu
Front End Developer

Given a 2D integer array matrix, return the transpose of matrix.

The transpose of a matrix is the matrix flipped over its main diagonal, switching the matrix's row and column indices. link: https://leetcode.com/problems/transpose-matrix/

Example

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [[1,4,7],[2,5,8],[3,6,9]]

Example 2:

Input: matrix = [[1,2,3],[4,5,6]] Output: [[1,4],[2,5],[3,6]]

/**
 * @param {number[][]} matrix
 * @return {number[][]}
 */
var transpose = function (matrix) {
  if (!matrix.length) return;
  const numOfCols = matrix[0].length;
  const numOfRows = matrix.length;
  const result = [];
  for (let i = 0; i < numOfCols; i++) {
    result.push([]);
  }
  for (let i = 0; i < numOfCols; i++) {
    for (let j = 0; j < numOfRows; j++) {
      result[i][j] = matrix[j][i];
    }
  }
  return result;
};

Interestingly enough, [3, 0, -2, -1, 1, 2].sort() gives [ -1, -2, 0, 1, 2, 3 ]

1390. Four Divisors

· One min read
Shi Xinyu
Shi Xinyu
Front End Developer

Given an integer array nums, return the sum of divisors of the integers in that array that have exactly four divisors. If there is no such integer in the array, return 0.

Example

Example 1:

Input: nums = [21,4,7] Output: 32

Explanation: 21 has 4 divisors: 1, 3, 7, 21 4 has 3 divisors: 1, 2, 4 7 has 2 divisors: 1, 7 The answer is the sum of divisors of 21 only.

Example 2:

Input: nums = [21,21] Output: 64

Example 3:

Input: nums = [1,2,3,4,5] Output: 0

Constraints:

1 <= nums.length <= 104 1 <= nums[i] <= 105

/**
 * @param {number[]} nums
 * @return {number}
 */

const findDivisors = (num) => {
  const divisors = [1, num];
  const upperLimit = Math.sqrt(num);
  if (Number.isInteger(upperLimit)) {
    return [];
    // divisors.push(upperLimit)
  }
  for (let i = 2; i < upperLimit; i++) {
    if (Number.isInteger(num / i)) {
      divisors.push(i);
      divisors.push(num / i);
    }
    if (divisors.length > 4) {
      return [];
    }
  }
  if (divisors.length === 4) {
    return divisors;
  } else {
    return [];
  }
};
var sumFourDivisors = function (nums) {
  const res = [];
  const length = nums.length;
  for (let i = 0; i < length; i++) {
    res.push(findDivisors(nums[i]).reduce((prev, cur) => prev + cur, 0));
  }
  return res.reduce((prev, cur) => prev + cur, 0);
};

967. Numbers With Same Consecutive Differences

· One min read
Shi Xinyu
Shi Xinyu
Front End Developer

Given two integers n and k, return an array of all the integers of length n where the difference between every two consecutive digits is k. You may return the answer in any order.

Note that the integers should not have leading zeros. Integers as 02 and 043 are not allowed.

Example

Example 1:

Input: n = 3, k = 7 Output: [181,292,707,818,929] Explanation: Note that 070 is not a valid number, because it has leading zeroes. Example 2:

Input: n = 2, k = 1 Output: [10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98]

Constraints:

2 <= n <= 9 0 <= k <= 9

/**
 * @param {number} n
 * @param {number} k
 * @return {number[]}
 */
var numsSameConsecDiff = function (n, k) {
  let results = new Set();
  function travel(arr) {
    if (arr.length === n) {
      results.add(Number(arr.join("")));
    } else if (arr.length < n) {
      const last = arr[arr.length - 1];
      const plus = last + k;
      const minus = last - k;
      if (plus >= 0 && plus <= 9) {
        travel([...arr, plus]);
      }
      if (minus >= 0 && minus <= 9) {
        travel([...arr, minus]);
      }
    }
  }
  for (let i = 1; i < 10; i++) {
    travel([i]);
  }
  return [...results];
};

1464. Maximum Product of Two Elements in an Array

· One min read
Shi Xinyu
Shi Xinyu
Front End Developer

Given a 2D integer array matrix, return the transpose of matrix.

Given the array of integers nums, you will choose two different indices i and j of that array. Return the maximum value of (nums[i]-1)*(nums[j]-1).

Example

Example 1:

Input: nums = [3,4,5,2] Output: 12 Explanation: If you choose the indices i=1 and j=2 (indexed from 0), you will get the maximum value, that is, (nums[1]-1)(nums[2]-1) = (4-1)(5-1) = 3*4 = 12. Example 2:

Input: nums = [1,5,4,5] Output: 16 Explanation: Choosing the indices i=1 and j=3 (indexed from 0), you will get the maximum value of (5-1)*(5-1) = 16. Example 3:

Input: nums = [3,7] Output: 12

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProduct = function (nums) {
  nums.sort((a, b) => a - b);
  const len = nums.length;
  return (nums[len - 1] - 1) * (nums[len - 2] - 1);
};

253. Lowest Common Ancestor of a Binary Search Tree

· 2 min read
Shi Xinyu
Shi Xinyu
Front End Developer

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Example

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 Output: 6 Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 Output: 2 Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function (root, p, q) {
  let pPath = [];
  let qPath = [];
  let path = [];
  function travel(node) {
    if (node) {
      path.push(node);
      if (node === p) {
        pPath = path.slice(0);
      }
      if (node === q) {
        qPath = path.slice(0);
      }
      travel(node.left);
      travel(node.right);
      path.pop();
    }
  }
  travel(root);

  let i = 0;
  for (; i < pPath.length || i < qPath.length; i++) {
    if (pPath[i] !== qPath[i]) {
      break;
    }
  }
  return pPath[i - 1];
};

867. Transpose Matrix

· One min read
Shi Xinyu
Shi Xinyu
Front End Developer

Given a 2D integer array matrix, return the transpose of matrix.

The transpose of a matrix is the matrix flipped over its main diagonal, switching the matrix's row and column indices. link: https://leetcode.com/problems/transpose-matrix/

Example

Example 1:

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [[1,4,7],[2,5,8],[3,6,9]]

Example 2:

Input: matrix = [[1,2,3],[4,5,6]] Output: [[1,4],[2,5],[3,6]]

/**
 * @param {number[][]} matrix
 * @return {number[][]}
 */
var transpose = function (matrix) {
  if (!matrix.length) return;
  const numOfCols = matrix[0].length;
  const numOfRows = matrix.length;
  const result = [];
  for (let i = 0; i < numOfCols; i++) {
    result.push([]);
  }
  for (let i = 0; i < numOfCols; i++) {
    for (let j = 0; j < numOfRows; j++) {
      result[i][j] = matrix[j][i];
    }
  }
  return result;
};