LeetCode 15. 3Sum

The Problem

Link to original problem on Leetcode.

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.

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

Input: nums = []
Output: []

Input: nums = [0]
Output: []

My Solution

This problem is tricky. Trickier than Two Sum, to be sure.

We can solve this problem in $O(n{^2} + n \log n)$ time, which reduces to just $O(n{^2})$. First we’ll sort the input array, which costs us the $O(n \log n)$ time but greatly reduces the complexity of comparing values across the array.

With our array sorted, we’ll iterate through it. For each number nums[i], we’ll designate a new index j and k representing the indices immediately right of i and at nums.length - 1 respectively. Then with a while loop, we increment j to see if any sum of nums[i] + nums[j] + nums[k] equals our target. If we find the correct sum, we can push to an array containing our results and then increment j and decrement k to search for new possible solutions. Once all the combinations of nums[i] + nums[j] + nums[k] have been exhausted, finally the for loop increments i and we start again. This process gives us $O(n{^2})$ time complexity.

const threeSum = (nums, target = 0) => {
	// Don't waste time doing anything if not enough values
	if (nums.length < 3) return [];

	// Sort nums to make traversal easier when dealing with
	// possible duplicates. Take O(N log(N)) time. Using a sort
	// function is key, or it will default to string comparison
	// which coulb be wrong.
	// DO NOT dedupe the array upfront, because you'll miss
	// correct combinations that include multiple instances of
	// the same number in the nums array.
	nums.sort((a, b) => a - b);
	const triplets = [];

	for (let i = 0; i < nums.length - 2; i++) {
		// Because we sorted nums, if nums[i] > target, we know we
		// cannot hit the target by continuing the loop.
		if (nums[i] > target) break;

		// To avoid duplicates in our triplets array, skip
		// duplicates of nums[i].
		if (i > 0 && nums[i] === nums[i - 1]) continue;

		// The variable j will represent an increasing index to the
		// immediate right of i. And k will represent a decreasing
		// index beginning at the end of the array.
		let j = i + 1;
		let k = nums.length - 1;

		// Think of i and k as anchored values, with j iterating
		// between them. Once j has gone through all of the space
		// between i and k, then k will decrement. Once k has
		// decremented all the way back such that
		// i === j - 1 === k - 2, i will increment and we repeat.
		while (j < k) {
			const sum = nums[i] + nums[j] + nums[k];

			if (sum === target) {
				// If we've got a target sum, push to results.
				triplets.push([nums[i], nums[j], nums[k]]);

				// To avoid adding duplicated, we reposition
				// j and k if their neighbors have the same value.
				while (nums[j] === nums[j + 1]) {
					j++;
				}
				while (nums[k] === nums[k - 1]) {
					k--;
				}

				// Now that we're sure we've skipped duplicates,
				// reposition j and k to begin a loop with fresh values.
				j++;
				k--;
				// Otherwise increment j until the sum is too great,
				// at which point we might as well stop incrementing
				// j because there's no way to hit the target sum
				// by continuing that loop.
			} else if (sum < target) {
				j++;
				// Finally, decrement k if j is exhausted.
			} else {
				k--;
			}
		}
	}

	return triplets;
};

Credit to uplifted for his example shared example here.