Four Sum
Receives an array of integers and a target value, and returns every unique quadruplet of values from the array that adds up to the target. It first sorts the array, then fixes the first two elements with nested loops (i, j) and searches the remaining range with two pointers moving inward from both ends: if the four-value sum is too small the left pointer advances, if too large the right pointer retreats, and if it matches the quadruplet is recorded before both pointers skip past any duplicate values. Each of the four loop levels (i, j, left, right) also skips over a value equal to its predecessor at the same level, which is what keeps the result free of duplicate quadruplets even when the input has repeated numbers. Returns a new array of four-value arrays in the order they were found; returns an empty array when no quadruplet sums to the target.
Visualization
- Input
- Result
Algorithm code
// Four Sum — a single pure function. Receives an array of integers and a
// target value, and returns every unique quadruplet of values from the array
// that adds up to the target, using a sort plus fixed-pair-plus-two-pointer
// scan, skipping duplicate values at every loop level to avoid duplicate
// quadruplets in the result.
/**
* @param {number[]} arr - array of integers
* @param {number} target - the target sum
* @returns {number[][]} every unique quadruplet of values summing to target
*/
export function fourSum(arr, target) {
const sorted = [...arr].sort((a, b) => a - b);
const n = sorted.length;
const result = [];
for (let i = 0; i < n - 3; i += 1) {
if (i > 0 && sorted[i] === sorted[i - 1]) continue;
for (let j = i + 1; j < n - 2; j += 1) {
if (j > i + 1 && sorted[j] === sorted[j - 1]) continue;
let left = j + 1;
let right = n - 1;
while (left < right) {
const sum = sorted[i] + sorted[j] + sorted[left] + sorted[right];
if (sum === target) {
result.push([sorted[i], sorted[j], sorted[left], sorted[right]]);
while (left < right && sorted[left] === sorted[left + 1]) left += 1;
while (left < right && sorted[right] === sorted[right - 1]) right -= 1;
left += 1;
right -= 1;
} else if (sum < target) {
left += 1;
} else {
right -= 1;
}
}
}
}
return result;
}FUNCTION fourSum(arr, target):
sorted ← SORT(arr) ascending
n ← length(sorted)
result ← empty list
FOR i ← 0 TO n - 4:
IF i > 0 AND sorted[i] = sorted[i - 1]:
CONTINUE
FOR j ← i + 1 TO n - 3:
IF j > i + 1 AND sorted[j] = sorted[j - 1]:
CONTINUE
left ← j + 1
right ← n - 1
WHILE left < right:
sum ← sorted[i] + sorted[j] + sorted[left] + sorted[right]
IF sum = target:
APPEND [sorted[i], sorted[j], sorted[left], sorted[right]] TO result
WHILE left < right AND sorted[left] = sorted[left + 1]:
left ← left + 1
WHILE left < right AND sorted[right] = sorted[right - 1]:
right ← right - 1
left ← left + 1
right ← right - 1
ELSE IF sum < target:
left ← left + 1
ELSE:
right ← right - 1
RETURN result