Sum Problem - Find All Unique Triplets That Sum to Zero

Question

## Problem

Given an integer array `nums`, return all unique triplets `[a, b, c]` such that `a + b + c == 0`. The solution set must not contain duplicate triplets.

```python
def three_sum(nums: List[int]) -> List[List[int]]:
    ...
```

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

Input:  nums=[0, 0, 0]
Output: [[0, 0, 0]]

Input:  nums=[1, 2, 3]
Output: []
```

## Approach

Sort `nums`. For each index `i`, use two pointers `lo = i+1` and `hi = len-1`. Skip duplicates at each pointer. Move `lo` right or `hi` left based on whether the sum is too small or too large.

Time: O(n^2). Space: O(1) excluding output.

## Follow-ups

1. Generalize to four-sum (4 elements summing to a target `k`).
2. How would you approach this if the array is a stream and you cannot sort it upfront?
3. What changes if the array contains duplicates and you must count all triplets (not unique)?
4. Can you solve 3-sum in better than O(n^2)? What is the lower bound?

Sum Problem - Find All Unique Triplets That Sum to Zero

Question Details

Full Details

Topics

More from C3 AI