3Sum — DSA-30

3Sum medium

Description

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, j != k, and nums[i] + nums[j] + nums[k] == 0.

The solution set must not contain duplicate triplets.

Examples

> Case 1:
    nums = [-1, 0, 1, 2, -1, -4]
    Output: [[-1, -1, 2], [-1, 0, 1]]
 
> Case 2:
    nums = [0, 1, 1]
    Output: []
 
> Case 3:
    nums = [0, 0, 0]
    Output: [[0, 0, 0]]

Constraints

3 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5

State design

The textbook K-Sum reduction: sort, fix one index, then opposite-ends two-pointer on the rest.

Sort the input so the convergence argument works AND duplicates are adjacent (for dedup).
For each i from 0 to n - 3:
- If nums[i] == nums[i - 1], skip (avoids duplicate first elements).
- Set l = i + 1, r = n - 1, target = -nums[i].
- Run two-pointer to find pairs summing to target.
- On a match: record, advance both, skip duplicates on each side.

The three deduplication points are the trickiest part — get any wrong and the output contains duplicates.

Code

⚠️

The three dedup points are not optional and not redundant:

Dedup #1 (skip duplicate i): without it, fixing the same value for i would re-run the same two-pointer pass and re-emit triplets.
Dedup #2/#3 (skip after match): without them, on input like [0, 0, 0, 0], the match at (l, r) would be followed by another match at (l + 1, r - 1) with identical values — duplicate triplet.

All three guards are required. Miss one and you produce duplicates.

The `nums[i] > 0` early exit

Once the smallest of three numbers (nums[i], after sorting) is positive, the sum of three numbers >= nums[i] > 0 can never be zero. Break out of the outer loop. A small but cheap optimization that helps on inputs with many positives at the end.

Analysis

Time: O(n²). Sort is O(n log n); the outer loop runs n times, each invoking an O(n) two-pointer pass.
Space: O(1) extra (excluding the output and sort’s intrinsic stack space).

Same skin

3Sum Closest — find the triplet whose sum is closest to a given target. Same template; track abs(sum − target) instead of equality.
3Sum Smaller — count triplets with sum < target. When sum < target at (l, r), all (l, l+1), ..., (l, r - 1) also work — add r - l to the count and advance l.
4Sum — fix two indices, run two-pointer on the rest. O(n³) time.
K-Sum (general) — recursive reduction down to two-sum.

Container With Most Water Remove Duplicates from Sorted Array