# Leetcode Problem 15: 3 Sum

Problem description:

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]] Explanation: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0. The distinct triplets are [-1,0,1] and [-1,-1,2]. Notice that the order of the output and the order of the triplets does not matter.`

`Example 2: Input: nums = [0,1,1] Output: [] Explanation: The only possible triplet does not sum up to 0. Example 3: Input: nums = [0,0,0] Output: [[0,0,0]] Explanation: The only possible triplet sums up to 0. ```ruby`

Constraints:

```
3 <= nums.length <= 3000
-105 <= nums[i] <= 105
```

As usual my priority is to get any solution at all, even if inefficient. The first code attempt
uses the *N choose K* formula from combinatorics. The problem description really can be reworded
roughly as “out of all the possible distinct triplets within the array, choose the ones that sum
to zero”.

### (Attempted) combinatorial Python solution Link to heading

```
# leetcode_15.py
from itertools import combinations
class Solution:
def threeSum(self, nums: list[int]) -> list[list[int]]:
n = len(nums)
if n < 3:
return []
result = []
index_range = list(range(0, n))
triplets = list(combinations(index_range, 3))
for triplet in triplets:
a, b, c = nums[triplet[0]], nums[triplet[1]], nums[triplet[2]]
if a + b + c == 0:
valid = sorted([a, b, c])
if valid not in result:
result.append(valid)
return result
```

I was so proud of myself until I was greeted with:

```
Memory Limit Exceeded
```

I tried to make this work with combinatorics but my implementation was either too slow or too memory hungry. The trick to solving this neatly is realising that this requires a slight modification from the Two Sum problem with input array sorted (Problem 167).

### Solution Link to heading

```
# leetcode_15.py
class Solution:
def threeSum(self, nums: list[int]) -> list[list[int]]:
n = len(nums)
sorted_nums = sorted(nums)
triplets = []
for i in range(0, n):
# skip duplicates
if i > 0 and sorted_nums[i] == sorted_nums[i - 1]:
continue
# from here on it follows from the TwoSum exercise with
# input array sorted (Problem 167)
l = i + 1
r = n - 1
while l < r:
sigma = sorted_nums[i] + sorted_nums[l] + sorted_nums[r]
if sigma > 0:
r -= 1
elif sigma == 0:
triplets.append([sorted_nums[i], sorted_nums[l], sorted_nums[r]])
l += 1
while sorted_nums[l] == sorted_nums[l - 1] and l < r:
l += 1
elif sigma < 0:
l += 1
return triplets
```

##### Python statistics Link to heading

```
Runtime: 1133 ms - beats 65.34 % of python3 submissions..
Memory Usage: 18.2 MB - beats 22.07 % of python3 submissions.
```

##### Complexity analysis Link to heading

Time: $ O(n) $, because of the loop.

Space: $ O(n) $ where $ n $ is the length of the input array sorted. There’s additional space required for the result

`triplets`

array, but it’s negligible compared to the cost of sorting the input array. To save space we could sort the array in place, but I’m ok with this solution.

Share on: