4Sum

MEDIUM✓ CHIP-TIMEDLC #18 — FULL STATEMENT ↗

The drill: Find every distinct set of four values in an array that adds up to a target sum — no value-quadruplet repeated, even when built from different positions.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

An array of integers and a target sum arrive together, and the task is to surface every combination of four distinct positions whose values add up to that target.

As with its three-value cousin, what matters is the quadruplet of values, not the positions that produced them — the same four numbers found through different positions still counts as one answer.

Order within a quadruplet and order among the quadruplets returned doesn't affect correctness; only the distinct set of value-quadruplets matters.

EX 01

nums = [1, 0, -1, 0, -2, 2] · target = 0

→ [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

MIX OF POSITIVES, NEGATIVES, AND DUPLICATE ZEROS

EX 02

nums = [2, 2, 2, 2, 2] · target = 8

→ [[2, 2, 2, 2]]

EVERY VALUE IDENTICAL, STILL ONE QUADRUPLET

EX 03

nums = [1, 2, 3, 4] · target = 10

→ [[1, 2, 3, 4]]

MINIMUM SIZE, USES EVERY ELEMENT

array length runs up to a couple hundred elements
values and the target can be negative, zero, or positive
each quadruplet must use four distinct positions in the array
duplicate value-quadruplets must be collapsed to one entry each

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Four nested loops check every quadruple directly, but that re-derives a smaller sum problem you already know how to solve fast. What does fixing two of the four values reduce this to?

HINT 2 THE STRUCTURE

Sort the array. Fix the first two values as anchors with nested loops, and the remaining two become a two-sum on a sorted suffix — closable with inward pointers.

HINT 3 ONE STEP FROM THE ANSWER

For each pair of anchors, walk lo from just past the second anchor and hi from the end: sum too small, push lo right; too big, pull hi left; equal, record the quadruplet and skip past duplicate values on both sides before continuing.

COACH'S BOARD — THE PATTERN, STEP BY STEP

TWO ANCHORS, TWO POINTERSPATTERN · SORT + TWO ANCHORSnums = [-2, -1, 0, 0, 1, 2] (sorted for the walk) · target = 0

-2

-1

STEP 1

Sorted: [-2, -1, 0, 0, 1, 2], target 0. Fix two anchors i and j, close the rest with two pointers.

STEP 1 / 10 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/4sum.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        out = []
        for i in range(n - 3):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            for j in range(i + 1, n - 2):
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                lo, hi = j + 1, n - 1
                while lo < hi:
                    s = nums[i] + nums[j] + nums[lo] + nums[hi]
                    if s < target:
                        lo += 1
                    elif s > target:
                        hi -= 1
                    else:
                        out.append([nums[i], nums[j], nums[lo], nums[hi]])
                        lo += 1
                        while lo < hi and nums[lo] == nums[lo - 1]:
                            lo += 1
                        hi -= 1
                        while lo < hi and nums[hi] == nums[hi + 1]:
                            hi -= 1
        return out

TIME O(N³)SPACE O(1)PYTHON · RACE PACE · 27 LN

class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        n = len(nums)
        found = set()
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    for l in range(k + 1, n):
                        if nums[i] + nums[j] + nums[k] + nums[l] == target:
                            found.add(tuple(sorted((nums[i], nums[j], nums[k], nums[l]))))
        return [list(quad) for quad in found]

TIME O(N⁴)SPACE O(N)PYTHON · TRAINING PACE · 11 LN

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> out = new ArrayList<>();
        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                int lo = j + 1;
                int hi = n - 1;
                while (lo < hi) {
                    long sum = (long) nums[i] + nums[j] + nums[lo] + nums[hi];
                    if (sum < target) {
                        lo++;
                    } else if (sum > target) {
                        hi--;
                    } else {
                        out.add(List.of(nums[i], nums[j], nums[lo], nums[hi]));
                        lo++;
                        while (lo < hi && nums[lo] == nums[lo - 1]) {
                            lo++;
                        }
                        hi--;
                        while (lo < hi && nums[hi] == nums[hi + 1]) {
                            hi--;
                        }
                    }
                }
            }
        }
        return out;
    }
}

TIME O(N³)SPACE O(1)JAVA · RACE PACE · 38 LN

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        int n = nums.length;
        Set<List<Integer>> found = new HashSet<>();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    for (int l = k + 1; l < n; l++) {
                        long sum = (long) nums[i] + nums[j] + nums[k] + nums[l];
                        if (sum == target) {
                            List<Integer> quad = new ArrayList<>(List.of(nums[i], nums[j], nums[k], nums[l]));
                            Collections.sort(quad);
                            found.add(quad);
                        }
                    }
                }
            }
        }
        return new ArrayList<>(found);
    }
}

TIME O(N⁴)SPACE O(N)JAVA · TRAINING PACE · 21 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED