018. 4Sum

Quick Identifier

Topic: two-pointers
Pattern: sort + two anchors + two-pointer pair search
Difficulty: Medium
Companies: Amazon, Google, Meta, Microsoft, Bloomberg
Frequency: High
LeetCode: 18
Hint: Fix two values, then solve a sorted Two Sum problem for the remaining suffix.

Quick Sights

Time Complexity: O(n^3) - two anchors plus one linear sweep.
Space Complexity: O(1) extra excluding output.
Core Mechanism: Sort, choose first and second, sweep left/right, and skip duplicates at every level.

Concept Explanation

4Sum is not a new idea. It is 3Sum with one extra fixed value. After two anchors, the remaining problem is sorted 2Sum.

The teaching point is duplicate discipline: skip duplicate first anchors, duplicate second anchors, and duplicate pair values after recording a quadruplet. This gives unique output without a global dedupe set.

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

Four loops are O(n^4). Pair-sum hashing uses extra memory and has complex dedupe. Two anchors plus two pointers is the interview-standard O(n^3) solution.

Optimal Solution

JavaScript

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

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

			while (left < right) {
				const sum = nums[first] + nums[second] + nums[left] + nums[right];
				if (sum === target) {
					out.push([nums[first], nums[second], 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 < target) left++;
				else right--;
			}
		}
	}

	return out;
}

Go

import "sort"

func fourSum(nums []int, target int) [][]int {
	sort.Ints(nums)
	out := [][]int{}
	for first := 0; first < len(nums)-3; first++ {
		if first > 0 && nums[first] == nums[first-1] { continue }
		for second := first + 1; second < len(nums)-2; second++ {
			if second > first+1 && nums[second] == nums[second-1] { continue }
			left, right := second+1, len(nums)-1
			for left < right {
				sum := nums[first] + nums[second] + nums[left] + nums[right]
				if sum == target {
					out = append(out, []int{nums[first], nums[second], 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 < target { left++ } else { right-- }
			}
		}
	}
	return out
}