4Sum Medium 0 attempts
LeetCode ↗

4Sum

Medium ArrayTwo Pointers LeetCode

You're given an array nums of n integers and a target value target. Find every distinct quadruplet of indices a, b, c, d (all different, each between 0 and n - 1) whose values nums[a] + nums[b] + nums[c] + nums[d] add up to target, and return the quadruplets themselves as [nums[a], nums[b], nums[c], nums[d]]. Each quadruplet in the result should be unique.

Input Format
Implement fourSum(nums, target). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement. The order of the outer result array does not matter. Order inside each group does not matter either.

Sample Input and Output

Example 1 · Run Sample

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]]
Constraints
  • 1 <= nums.length <= 200
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9
Test Cases (2)
Case 1
Args: [[1,0,-1,0,-2,2],0] Expected: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Case 2
Args: [[2,2,2,2,2],8] Expected: [[2,2,2,2]]
Topics
ArrayTwo Pointers

Sort the array. Use two nested loops to fix the first two numbers, then use two pointers to find the remaining two. Skip duplicates at every level to avoid duplicate quadruplets.

javascript
function fourSum(nums, target) {
  nums.sort((a, b) => a - b);
  const result = [];
  const n = nums.length;

  for (let i = 0; i < n - 3; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    for (let j = i + 1; j < n - 2; j++) {
      if (j > i + 1 && nums[j] === nums[j - 1]) continue;
      let left = j + 1, right = n - 1;
      while (left < right) {
        const sum = nums[i] + nums[j] + nums[left] + nums[right];
        if (sum === target) {
          result.push([nums[i], nums[j], nums[left], nums[right]]);
          while (left < right && nums[left] === nums[left + 1]) left++;
          while (left < right && nums[right] === nums[right - 1]) right--;
          left++;
          right--;
        } else if (sum < target) left++;
        else right--;
      }
    }
  }

  return result;
}

Time: O(n³) Space: O(1) (ignoring output)

Saved in this browser only. Private to you.

JavaScript