3Sum

Given an integer array nums, return all unique triplets [a, b, c] such that a + b + c == 0. Each triplet should be in non-decreasing order, and the overall order of triplets does not matter.

A naive triple loop is O(n^3). Sorting plus two pointers reduces it to O(n^2).

Why this is worth learning

Fixing one value converts a three-variable search into a sorted two-variable search. Uniqueness is about value triples, not distinct index combinations.

Before coding: one-minute experiment

How many triples should [0,0,0,0] return, and how many indices does each triple consume?

Function signature

func ThreeSum(nums []int) [][]int

Inputs / outputs

• nums: input slice of integers.
• Return: slice of unique triplets that sum to zero.

Example

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

Constraints

• 0 <= len(nums) <= 3000
• -100_000 <= nums[i] <= 100_000

Core idea (near-solution)

Sort the array. For each index i, solve a 2-sum problem on the subarray to the right using two pointers.

Invariants:

• The array is sorted, so moving pointers changes the sum monotonically.
• Duplicates must be skipped to avoid repeated triplets.

Algorithm (step-by-step)

1. Sort nums.
2. For each i from 0 to len(nums)-3:
   • Skip i if it is a duplicate of i-1.
   • Set l = i+1, r = len(nums)-1.
   • While l < r:
     • Compute sum = nums[i] + nums[l] + nums[r].
     • If sum == 0, record the triplet, then move l and r past duplicates.
     • If sum < 0, increment l.
     • If sum > 0, decrement r.
3. Return the collected triplets.

Correctness sketch

For each distinct anchor value, the inner two-pointer scan considers all possible complementary value pairs by the sorted pair-discard argument. Any sorted zero-sum triple has a smallest value that appears as some anchor, so no valid triple is missed. Once a match is found, every equal left or right value would reproduce the same value triple, so skipping those runs removes only duplicates. Skipping equal anchors similarly prevents repetition across outer iterations. The three positions are distinct because i<l<r. Every emitted triple is sorted and sums to zero, proving both soundness and completeness.

Trace (hand walkthrough)

Example input:
nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Walk:
- sort -> [-4,-1,-1,0,1,2]
- i=1 (-1), l=2 (-1), r=5 (2): sum=0 -> add [-1,-1,2]
- move l=3 (0), r=4 (1): sum=0 -> add [-1,0,1]
- other i values give no new triples

Pitfalls to avoid

• Forgetting to skip duplicates at i, l, and r.
• Returning triplets in an unsorted order (keep the sorted array order).

Debugging lens

Normalize only the outer result order in assertions; each returned row must already be non-decreasing. Test a duplicate-heavy array containing several different valid triples. The reference sorts nums in place.

Complexity

Time: O(n log n+n^2), usually written O(n^2). Auxiliary space: O(log n) sorting stack for the supplied sort, plus O(1) scan state. Output storage: O(z), where z is the number of returned triples.

Implementation notes (Go)

• Use sort.Ints on nums.
• Each returned triplet must already be sorted. Tests may normalize the outer list order, but sorting the returned rows would hide a contract violation.

Contract precision

The reference sorts the caller's nums slice. The overall result order is unspecified; each triple is sorted and unique.

Reconstruction checkpoint

How many triples should [0,0,0,0] return, and how many indices does each triple consume?

Return to Two Pointers · Module quiz