018. 4Sum

At a Glance

Topic: two-pointers
Pattern: Two Pointers
Difficulty: Medium
Companies: Amazon, Google, Meta, Microsoft, Bloomberg
Frequency: High
LeetCode: 18

Problem (one-liner)

Given an array of integers nums and a target, return all unique quadruplets [a,b,c,d] such that a+b+c+d == target. No duplicate quadruplets in the output.

Recognition Cues

Four numbers summing to target (generalization of 3Sum)
"Unique quadruplets" → sort and skip duplicates at each level
Often O(n³) with careful pruning

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 — four nested loops + dedupe.
Better — sort + double loop anchors + two pointers — O(n³) time / O(1) extra beyond output.
Optimal — same O(n³) for comparison-based approach on arbitrary integers.

Optimal Solution

Go

import "sort"

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

JavaScript

function fourSum(numbers, target) {
	numbers.sort((a, b) => a - b);
	const quadruplets = [];
	const length = numbers.length;
	for (let first = 0; first < length - 3; first++) {
		if (first > 0 && numbers[first] === numbers[first - 1]) {
			continue;
		}
		for (let second = first + 1; second < length - 2; second++) {
			if (second > first + 1 && numbers[second] === numbers[second - 1]) {
				continue;
			}
			let left = second + 1;
			let right = length - 1;
			while (left < right) {
				const sum =
					numbers[first] +
					numbers[second] +
					numbers[left] +
					numbers[right];
				if (sum === target) {
					quadruplets.push([
						numbers[first],
						numbers[second],
						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 < target) {
					left++;
				} else {
					right--;
				}
			}
		}
	}
	return quadruplets;
}