Skip to main content

2 posts tagged with "sort"

View All Tags

15. 3Sum

· 2 min read
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(","));
}

253. Lowest Common Ancestor of a Binary Search Tree

· 2 min read
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];
};