015. 3Sum

At a Glance

Topic: two-pointers
Pattern: Two Pointers
Difficulty: Medium
Companies: Amazon, Google, Meta, Bloomberg, Adobe
Frequency: Very High
LeetCode: 15

Given an integer array, return all unique triplets [a, b, c] such that a + b + c == 0. Order within triplets and among triplets follows typical LeetCode expectations (sort outer loop and skip duplicates).

Recognition Cues

"Three numbers sum to zero / target"
"Find all unique triplets"
Unsorted array → sort unlocks two-pointer sweep

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Brute force — O(n³) time / O(1) space — three nested loops + dedupe set.
Better — sort + for each anchor, two pointers — O(n²) time / O(1) extra beyond output — standard interview solution.
Optimal — same as better for this model — O(n²) time / O(1) auxiliary if output not counted.

Optimal Solution

Go

import "sort"

func threeSum(nums []int) [][]int {
	sort.Ints(nums)
	n := len(nums)
	out := [][]int{}
	for anchor := 0; anchor < n-2; anchor++ {
		if anchor > 0 && nums[anchor] == nums[anchor-1] {
			continue
		}
		left, right := anchor+1, n-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
}

JavaScript

function threeSum(numbers) {
	numbers.sort((a, b) => a - b);
	const triplets = [];
	const length = numbers.length;
	for (let anchor = 0; anchor < length - 2; anchor++) {
		if (anchor > 0 && numbers[anchor] === numbers[anchor - 1]) {
			continue;
		}
		let left = anchor + 1;
		let right = length - 1;
		while (left < right) {
			const sum = numbers[anchor] + numbers[left] + numbers[right];
			if (sum === 0) {
				triplets.push([
					numbers[anchor],
					numbers[left],
					numbers[right],
				]);
				while (left < right && numbers[left] === numbers[left + 1]) {
					left++;
				}
				while (left < right && numbers[right] === numbers[right - 1]) {
					right--;
				}
				left++;
				right--;
			} else if (sum < 0) {
				left++;
			} else {
				right--;
			}
		}
	}
	return triplets;
}