Problem Statement

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 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}

## Solution

This problem is a follow-up of Two Sum, and it is a good idea to first take a look at Two Sum and Two Sum II. An interviewer may ask to solve Two Sum first, and then throw 3Sum at you. Pay attention to subtle differences in problem description and try to re-use existing solutions!

Two Sum, Two Sum II and 3Sum share a similarity that the sum of elements must match the target exactly. A difference is that, instead of exactly one answer, we need to find all unique triplets that sum to zero.

Before jumping in, let’s check the existing solutions and determine the best conceivable runtime (BCR) for 3Sum:

- Two Sum uses a hashmap to find complement values, and therefore achieves time complexity.
- Two Sum II uses the two pointers pattern and also has time complexity for a sorted array. We can use this approach for any array if we sort it first, which bumps the time complexity to .

Considering that there is one more dimension in 3Sum, it sounds reasonable to shoot for time complexity as our BCR.

#### Approach 1: Two Pointers

We will follow the same two pointers pattern as in Two Sum II. It requires the array to be sorted, so we’ll do that first. As our BCR is \mathcal{O}(n^2)O(*n*2), sorting the array would not change the overall time complexity.

To make sure the result contains unique triplets, we need to skip duplicate values. It is easy to do because repeating values are next to each other in a sorted array.

If you are wondering how to solve this problem without sorting the array, go over the “No-Sort” approach below. There are cases when that approach is preferable, and your interviewer may probe your knowledge there.

After sorting the array, we move our pivot element `nums[i]`

and analyze elements to its right. We find all pairs whose sum is equal `-nums[i]`

using the two pointers pattern, so that the sum of the pivot element (`nums[i]`

) and the pair (`-nums[i]`

) is equal to zero.

As a quick refresher, the pointers are initially set to the first and the last element respectively. We compare the sum of these two elements to the target. If it is smaller, we increment the lower pointer `lo`

. Otherwise, we decrement the higher pointer `hi`

. Thus, the sum always moves toward the target, and we “prune” pairs that would move it further away. Again, this works only if the array is sorted. Head to the Two Sum II solution for the detailed explanation.

**Algorithm**

The implementation is straightforward – we just need to modify `twoSumII`

to produce triplets and skip repeating values.

- For the main function:
- Sort the input array
`nums`

. - Iterate through the array:
- If the current value is greater than zero, break from the loop. Remaining values cannot sum to zero.
- If the current value is the same as the one before, skip it.
- Otherwise, call
`twoSumII`

for the current position`i`

.

- Sort the input array
- For
`twoSumII`

function:- Set the low pointer
`lo`

to`i + 1`

, and high pointer`hi`

to the last index. - While low pointer is smaller than high:
- If
`sum`

of`nums[i] + nums[lo] + nums[hi]`

is less than zero, increment`lo`

. - If
`sum`

is greater than zero, decrement`hi`

. - Otherwise, we found a triplet:
- Add it to the result
`res`

. - Decrement
`hi`

and increment`lo`

. - Increment
`lo`

while the next value is the same as before to avoid duplicates in the result.

- Add it to the result

- If

- Set the low pointer
- Return the result
`res`

.

class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: res = [] nums.sort() for i in range(len(nums)): if nums[i] > 0: break if i == 0 or nums[i - 1] != nums[i]: self.twoSumII(nums, i, res) return res def twoSumII(self, nums: List[int], i: int, res: List[List[int]]): lo, hi = i + 1, len(nums) - 1 while (lo < hi): sum = nums[i] + nums[lo] + nums[hi] if sum < 0: lo += 1 elif sum > 0: hi -= 1 else: res.append([nums[i], nums[lo], nums[hi]]) lo += 1 hi -= 1 while lo < hi and nums[lo] == nums[lo - 1]: lo += 1

**Complexity Analysis**

- Time Complexity: .
`twoSumII`

is , and we call it times. Sorting the array takes , so overall complexity is . This is asymptotically equivalent to . - Space Complexity: from to , depending on the implementation of the sorting algorithm. For the purpose of complexity analysis, we ignore the memory required for the output.