# 015. 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 - -10
^{5}<=`nums[i]`

<= 10^{5}

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

};