# 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.

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 = 
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(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.