Find four elements that sum to a given value (4-sum)

Medium

Problem

Return every unique quadruplet of values (from distinct indices) that sums to target. Do not repeat the same set of values.

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]]

Also asked as: find four elements that sum to a given value

Test cases

Case 1

Input:    [1,0,-1,0,-2,2], 0
Expected (any order): [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Case 2

Input:    [2,2,2,2,2], 8
Expected (any order): [[2,2,2,2]]

Case 3

Input:    [0,0,0,0], 0
Expected (any order): [[0,0,0,0]]

Case 4

Input:    [1,2,3], 6
Expected (any order): []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Sort + fix two + two pointers

Time O(n³)Space O(1)

Two nested loops fix a and b; a two-pointer scan finds c, d for the remaining target. Skip duplicates.

function fourSum(a, target) {
a.sort((x, y) => x - y);
const res = [];
const n = a.length;
for (let i = 0; i < n - 3; i++) {
if (i && a[i] === a[i - 1]) continue;
for (let j = i + 1; j < n - 2; j++) {
if (j > i + 1 && a[j] === a[j - 1]) continue;
let l = j + 1, r = n - 1;
while (l < r) {
const s = a[i] + a[j] + a[l] + a[r];
if (s === target) {
res.push([a[i], a[j], a[l], a[r]]);
while (l < r && a[l] === a[l + 1]) l++;
while (l < r && a[r] === a[r - 1]) r--;
l++; r--;
} else if (s < target) l++;
else r--;
}
}
}
return res;
}