015. 3Sum

Quick Identifier

Topic: two-pointers
Pattern: sort + anchor + two-pointer pair search
Difficulty: Medium
Companies: Amazon, Google, Meta, Bloomberg, Adobe
Frequency: Very High
LeetCode: 15
Hint: Sort first. Freeze one value, then solve Two Sum II on the suffix while skipping duplicates.

Quick Sights

Time Complexity: O(n^2) - each anchor performs one linear sweep.
Space Complexity: O(1) extra excluding output; sorting internals vary by runtime.
Core Mechanism: Sort, skip duplicate anchors, use left/right to find pairs summing to -nums[anchor], and skip duplicate pair values after each hit.

Concept Explanation

3Sum is many 2Sum problems. Once one value is fixed as the anchor, the remaining two values must hit a known target.

Sorting gives both the movement rule and duplicate control. When the sum is too small, move left; when too large, move right. Duplicate triplets are avoided by skipping repeated anchors and repeated pair values after recording a hit.

Diagram

This diagram shows the pointer decisions and the step-by-step algorithm flow.

Loading diagram…

Study Pattern (SDE3+)

0-3 min: Name the pointer shape, then state the invariant and discard rule before coding.
Implementation pass: Keep pointer movement explicit; every branch must return, record an answer, or move at least one pointer.
5 min extension: Explain how the solution changes for immutable input, streaming input, many duplicate values, or many repeated queries.

Approaches

Three loops are O(n^3). Anchor plus hash set is O(n^2) but dedupe is messy. Sort plus two pointers is the standard O(n^2) solution.

Optimal Solution

JavaScript

function threeSum(nums) {
	nums.sort((a, b) => a - b);
	const out = [];

	for (let anchor = 0; anchor < nums.length - 2; anchor++) {
		if (anchor > 0 && nums[anchor] === nums[anchor - 1]) continue;
		let left = anchor + 1;
		let right = nums.length - 1;

		while (left < right) {
			const sum = nums[anchor] + nums[left] + nums[right];
			if (sum === 0) {
				out.push([nums[anchor], nums[left], nums[right]]);
				while (left < right && nums[left] === nums[left + 1]) left++;
				while (left < right && nums[right] === nums[right - 1]) right--;
				left++;
				right--;
			} else if (sum < 0) left++;
			else right--;
		}
	}

	return out;
}

Go

import "sort"

func threeSum(nums []int) [][]int {
	sort.Ints(nums)
	out := [][]int{}
	for anchor := 0; anchor < len(nums)-2; anchor++ {
		if anchor > 0 && nums[anchor] == nums[anchor-1] {
			continue
		}
		left, right := anchor+1, len(nums)-1
		for left < right {
			sum := nums[anchor] + nums[left] + nums[right]
			if sum == 0 {
				out = append(out, []int{nums[anchor], nums[left], nums[right]})
				for left < right && nums[left] == nums[left+1] { left++ }
				for left < right && nums[right] == nums[right-1] { right-- }
				left++
				right--
			} else if sum < 0 {
				left++
			} else {
				right--
			}
		}
	}
	return out
}