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.

Examples

Example 1:

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

Example 2:

Input: nums = []
Output: []

Example 3:

Input: nums = [0]
Output: []
Constraints
  • 0 <= nums.length <= 3000
  • -105 <= nums[i] <= 105

My Solution

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

We can solve this problem in O(n2+nlogn)O(n{^2} + n \log n) time, which reduces to just O(n2)O(n{^2}). First we'll sort the input array, which costs us the O(nlogn)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(n2)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.