4Sum

Medium
760.

4Sum

4Sum is a medium coding problem on arrays, sorting and two pointers, asked in Amazon, Google, Adobe and Rubrik interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
var fourSum = function(nums, target) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

4Sum — Solution in Python, Java & C++

4Sum solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem, asked at Amazon, Google and Adobe.

4Sum is a medium coding problem on arrays, sorting and two pointers, asked in Amazon, Google, Adobe and Rubrik interviews.

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

Hints for 4Sum

  1. Hint 1

    Sort first: it makes the two inner pointers work and gives the required output order for free.

  2. Hint 2

    Fix the two outer indices, then two-pointer the remaining suffix for the other pair.

  3. Hint 3

    Skip a repeated value at each of the four positions, or the same quadruplet is emitted many times.

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

Java

public static int[][] fourSum(int[] nums, int target) {
    int[] s = nums.clone();
    Arrays.sort(s);
    int n = s.length;
    List<int[]> out = new ArrayList<>();
    for (int i = 0; i < n - 3; i++) {
        if (i > 0 && s[i] == s[i - 1]) continue;
        for (int j = i + 1; j < n - 2; j++) {
            if (j > i + 1 && s[j] == s[j - 1]) continue;
            int lo = j + 1, hi = n - 1;
            while (lo < hi) {
                long sum = (long) s[i] + s[j] + s[lo] + s[hi];
                if (sum == target) {
                    out.add(new int[] { 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.toArray(new int[0][]);
}

C++

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    vector<int> s = nums;
    sort(s.begin(), s.end());
    int n = (int) s.size();
    vector<vector<int>> out;
    for (int i = 0; i + 3 < n; i++) {
        if (i > 0 && s[i] == s[i - 1]) continue;
        for (int j = i + 1; j + 2 < n; j++) {
            if (j > i + 1 && s[j] == s[j - 1]) continue;
            int lo = j + 1, hi = n - 1;
            while (lo < hi) {
                long long sum = (long long) s[i] + s[j] + s[lo] + s[hi];
                if (sum == target) {
                    out.push_back({ 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;
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms