Get started

4Sum — Medium Problem & Solution

Return all unique quadruplets [a, b, c, d] drawn from distinct indices of nums whose sum is target.

  • Difficulty: Medium
  • Topics: Arrays, Sorting, Two Pointers
  • Asked at: Amazon, Google, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Return all unique quadruplets [a, b, c, d] drawn from distinct indices of nums whose sum is target.

Each quadruplet must be sorted ascending, and the list of quadruplets must be sorted lexicographically.

Example 1

Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2

Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]
Explanation: Only one distinct quadruplet exists even though many index choices give it.

Example 3

Input: nums = [1,2,3], target = 6
Output: []
Explanation: Fewer than four elements.

Constraints

  • 1 <= nums.length <= 200
  • -100000000 <= nums[i] <= 100000000
  • -100000000 <= target <= 100000000

How to solve 4Sum

Reduce to the familiar two-pointer pattern by fixing the two smallest members. Sorting makes both the inner sweep and the deduplication straightforward.

Approach

  1. Sort nums.
  2. Loop i and then j over the first two positions, skipping a value equal to the previous one at that position.
  3. Two-pointer lo and hi over the remaining suffix, moving lo up when the sum is short and hi down when it is long.
  4. On a hit, record the quadruplet and skip past duplicates on both inner pointers before advancing.

Why it works

Sorting makes the sum monotone in each pointer, so the inner sweep visits every viable pair for a fixed (i, j) in linear time. Skipping equal values at each position is what makes each distinct quadruplet appear exactly once, and the scan order produces them lexicographically.

Complexity

  • Time — O(n³)
  • Space — O(n) beyond the output

Pitfalls

  • Deduplicating only the outer indices still emits repeats when the inner pair has equal values.
  • The four-way sum exceeds 32 bits at LeetCode's real limits — this version caps the values, but accumulating in 64 bits is the safe habit.
  • Arrays shorter than four elements must produce an empty list rather than an out-of-range read.

Reference solution

Python

from typing import List

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

JavaScript

var fourSum = function(nums, target) {
    var s = nums.slice().sort(function(a, b) { return a - b; });
    var n = s.length, out = [];
    for (var i = 0; i < n - 3; i++) {
        if (i > 0 && s[i] === s[i - 1]) continue;
        for (var j = i + 1; j < n - 2; j++) {
            if (j > i + 1 && s[j] === s[j - 1]) continue;
            var lo = j + 1, hi = n - 1;
            while (lo < hi) {
                var sum = s[i] + s[j] + s[lo] + s[hi];
                if (sum === target) {
                    out.push([s[i], s[j], s[lo], s[hi]]);
                    while (lo < hi && s[lo] === s[lo + 1]) lo++;
                    while (lo < hi && s[hi] === s[hi - 1]) hi--;
                    lo++;
                    hi--;
                } else if (sum < target) lo++;
                else hi--;
            }
        }
    }
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue