# 3Sum

- **Canonical ID**: `3sum`
- **Canonical URL**: https://dsacheatsheet.com/problems/3sum
- **Difficulty**: medium
- **Patterns**: Two Pointers
- **Version**: 1.0.0 (verified 2026-11-11T21:00:00Z)
- **Original Problem**: https://leetcode.com/problems/3sum/

## 1. Core Invariant / The Trick

Sort the array first (`O(N log N)`), fix anchor `nums[i]` (skipping duplicates and breaking early if `nums[i] > 0`), and run Two Pointers on `(i+1 .. N-1)` skipping duplicates on `l` after matches.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N^2)`
- **Space Complexity**: `O(1)`
- **Proof**: N outer anchors each run a linear O(N) two-pointer pass (ignoring output list space).

## 3. Minimal Idiomatic Code

### Python
```python
def threeSum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    res = []
    for i in range(len(nums) - 2):
        if nums[i] > 0: break
        if i > 0 and nums[i] == nums[i - 1]: continue
        l, r = i + 1, len(nums) - 1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s < 0: l += 1
            elif s > 0: r -= 1
            else:
                res.append([nums[i], nums[l], nums[r]])
                l += 1
                r -= 1
                while l < r and nums[l] == nums[l - 1]: l += 1
    return res
```

### TypeScript
```typescript
export function threeSum(nums: number[]): number[][] {
  nums.sort((a, b) => a - b);
  const res: number[][] = [];
  for (let i = 0; i < nums.length - 2; i++) {
    if (nums[i] > 0) break;
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    let l = i + 1, r = nums.length - 1;
    while (l < r) {
      const s = nums[i] + nums[l] + nums[r];
      if (s < 0) l++;
      else if (s > 0) r--;
      else {
        res.push([nums[i], nums[l], nums[r]]);
        l++; r--;
        while (l < r && nums[l] === nums[l - 1]) l++;
      }
    }
  }
  return res;
}
```

### C++
```cpp
vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    for (int i = 0; i < (int)nums.size() - 2 && nums[i] <= 0; ++i) {
        if (i > 0 && nums[i] == nums[i-1]) continue;
        int l = i + 1, r = nums.size() - 1;
        while (l < r) {
            int s = nums[i] + nums[l] + nums[r];
            if (s < 0) l++; else if (s > 0) r--;
            else {
                res.push_back({nums[i], nums[l++], nums[r--]});
                while (l < r && nums[l] == nums[l-1]) l++;
            }
        }
    }
    return res;
}
```

### Java
```java
List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    for (int i = 0; i < nums.length - 2 && nums[i] <= 0; i++) {
        if (i > 0 && nums[i] == nums[i-1]) continue;
        int l = i + 1, r = nums.length - 1;
        while (l < r) {
            int s = nums[i] + nums[l] + nums[r];
            if (s < 0) l++; else if (s > 0) r--;
            else {
                res.add(Arrays.asList(nums[i], nums[l++], nums[r--]));
                while (l < r && nums[l] == nums[l-1]) l++;
            }
        }
    }
    return res;
}
```

### Go
```go
func threeSum(nums []int) [][]int {
    sort.Ints(nums)
    var res [][]int
    for i := 0; i < len(nums)-2 && nums[i] <= 0; i++ {
        if i > 0 && nums[i] == nums[i-1] { continue }
        l, r := i+1, len(nums)-1
        for l < r {
            s := nums[i] + nums[l] + nums[r]
            if s < 0 { l++ } else if s > 0 { r-- } else {
                res = append(res, []int{nums[i], nums[l], nums[r]})
                l++; r--
                for l < r && nums[l] == nums[l-1] { l++ }
            }
        }
    }
    return res
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Failing to deduplicate `nums[i] == nums[i-1]` AND `nums[l] == nums[l-1]` emits duplicate triplets.

### Follow-ups
- k-Sum generalizes by recursive reduction down to sorted 2-Sum.