Four Sum Problem All Unique Quadruplets in DSA Javascript

Mental Model

Find four numbers in a list that add up to a target without repeating quadruplets. We use sorting and two pointers to efficiently find these groups.

Analogy: Imagine you have a group of friends and want to find all unique teams of four whose combined ages add up to a birthday target. You first sort them by age, then pick pairs and look for matching pairs to complete the team without repeating the same group.

Array: [1, 0, -1, 0, -2, 2]
Sorted: [-2, -1, 0, 0, 1, 2]
Indices: i -> 0, j -> 1, left -> 2, right -> 5
Goal: sum of values at i, j, left, right = target

Dry Run Walkthrough

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

Goal: Find all unique quadruplets that sum to 0

Step 1: Sort the array

[-2, -1, 0, 0, 1, 2]

Why: Sorting helps avoid duplicates and use two pointers efficiently

Step 2: Set i=0 (-2), j=1 (-1), left=2 (0), right=5 (2), calculate sum

Indices: i=0(-2), j=1(-1), left=2(0), right=5(2)
Sum = -2 + (-1) + 0 + 2 = -1

Why: Check if sum matches target; here sum < target, so move left pointer

Step 3: Move left pointer from 2 to 3 (0), recalc sum

Indices: i=0(-2), j=1(-1), left=3(0), right=5(2)
Sum = -2 + (-1) + 0 + 2 = -1

Why: Sum still less than target, move left pointer to increase sum

Step 4: Move left pointer from 3 to 4 (1), recalc sum

Indices: i=0(-2), j=1(-1), left=4(1), right=5(2)
Sum = -2 + (-1) + 1 + 2 = 0

Why: Sum equals target, record quadruplet [-2, -1, 1, 2]

Step 5: Move j to 2 (0), reset left=3 (0), right=5 (2), calc sum

Indices: i=0(-2), j=2(0), left=3(0), right=5(2)
Sum = -2 + 0 + 0 + 2 = 0

Why: Sum equals target, record quadruplet [-2, 0, 0, 2]

Step 6: Move i to 1 (-1), j=2 (0), left=3 (0), right=5 (2), calc sum

Indices: i=1(-1), j=2(0), left=3(0), right=5(2)
Sum = -1 + 0 + 0 + 2 = 1

Why: Sum greater than target, move right pointer left to decrease sum

Step 7: Move right pointer from 5 to 4 (1), recalc sum

Indices: i=1(-1), j=2(0), left=3(0), right=4(1)
Sum = -1 + 0 + 0 + 1 = 0

Why: Sum equals target, record quadruplet [-1, 0, 0, 1]

Result:

Unique quadruplets:
[-2, -1, 1, 2]
[-2, 0, 0, 2]
[-1, 0, 0, 1]

Annotated Code

DSA Javascript

class FourSum {
  static fourSum(nums, target) {
    nums.sort((a, b) => a - b); // sort array to handle duplicates and two pointers
    const quadruplets = [];
    const n = nums.length;
    for (let i = 0; i < n - 3; i++) {
      if (i > 0 && nums[i] === nums[i - 1]) continue; // skip duplicate i
      for (let j = i + 1; j < n - 2; j++) {
        if (j > i + 1 && nums[j] === nums[j - 1]) continue; // skip duplicate j
        let left = j + 1;
        let right = n - 1;
        while (left < right) {
          const sum = nums[i] + nums[j] + nums[left] + nums[right];
          if (sum === target) {
            quadruplets.push([nums[i], nums[j], nums[left], nums[right]]); // found quadruplet
            while (left < right && nums[left] === nums[left + 1]) left++; // skip duplicate left
            while (left < right && nums[right] === nums[right - 1]) right--; // skip duplicate right
            left++;
            right--;
          } else if (sum < target) {
            left++; // increase sum by moving left pointer right
          } else {
            right--; // decrease sum by moving right pointer left
          }
        }
      }
    }
    return quadruplets;
  }
}

// Driver code
const nums = [1, 0, -1, 0, -2, 2];
const target = 0;
const result = FourSum.fourSum(nums, target);
for (const quad of result) {
  console.log(quad.join(", ") + "\n");
}

nums.sort((a, b) => a - b);

sort array to handle duplicates and enable two pointer technique

if (i > 0 && nums[i] === nums[i - 1]) continue;

skip duplicate values for i to avoid repeated quadruplets

if (j > i + 1 && nums[j] === nums[j - 1]) continue;

skip duplicate values for j to avoid repeated quadruplets

while (left < right) { const sum = nums[i] + nums[j] + nums[left] + nums[right];

calculate sum of current quadruplet candidates

if (sum === target) { quadruplets.push([nums[i], nums[j], nums[left], nums[right]]);

found quadruplet matching target, add to result

while (left < right && nums[left] === nums[left + 1]) left++;

skip duplicates for left pointer

while (left < right && nums[right] === nums[right - 1]) right--;

skip duplicates for right pointer

left++; right--;

move pointers inward after recording quadruplet

else if (sum < target) { left++; } else { right--; }

adjust pointers to increase or decrease sum

Output

-2, -1, 1, 2

-2, 0, 0, 2

-1, 0, 0, 1

Complexity Analysis

Time: O(n^3) because we use two nested loops and a two-pointer scan inside

Space: O(k) where k is number of quadruplets found, for storing results

vs Alternative: Naive approach is O(n^4) by checking all quadruplets; this method is faster by sorting and two pointers

Edge Cases

Empty array

Returns empty list, no quadruplets found

DSA Javascript

for (let i = 0; i < n - 3; i++) {

Array with fewer than 4 elements

Returns empty list, no quadruplets possible

DSA Javascript

for (let i = 0; i < n - 3; i++) {

All elements are the same and sum matches target

Returns one quadruplet without duplicates

DSA Javascript

if (i > 0 && nums[i] === nums[i - 1]) continue;

When to Use This Pattern

When asked to find unique quadruplets summing to a target, use sorting plus two nested loops and two pointers to efficiently find all sets without duplicates.

Common Mistakes

Mistake: Not skipping duplicates for i, j, left, or right pointers causing repeated quadruplets
Fix: Add checks to skip duplicates after sorting for all pointers

Mistake: Not sorting the array first, making two pointer approach invalid
Fix: Always sort the array before starting the search

Mistake: Moving pointers incorrectly when sum equals target
Fix: After recording quadruplet, move both left and right pointers inward and skip duplicates

Summary

Finds all unique groups of four numbers that add up to a target sum.

Use when you need to find quadruplets with a specific sum efficiently without duplicates.

Sort the array and use two nested loops plus two pointers to find quadruplets while skipping duplicates.

Practice

1. What is the main goal of the Four Sum Problem in data structures and algorithms?

easy

A. Find all unique quadruplets in an array that sum up to a target value

B. Sort the array in ascending order

C. Find the maximum element in the array

D. Count the number of pairs with a given sum

Solution

1. Step 1: Understand the problem statement

   The Four Sum Problem asks us to find all unique groups of four numbers in an array that add up to a specific target sum.

2. Step 2: Differentiate from other problems

   This is different from sorting, finding max, or counting pairs because it specifically looks for quadruplets with a sum equal to the target.

3. Final Answer:

   Find all unique quadruplets in an array that sum up to a target value -> Option A

4. Quick Check:

   Four Sum Problem = Find quadruplets summing to target [OK]

Hint: Look for four numbers adding to target, not sorting or max [OK]

Common Mistakes:

• Confusing with sorting or max element problems
• Looking for pairs instead of quadruplets
• Ignoring uniqueness of quadruplets

2. Which of the following is the correct way to start sorting an array nums in JavaScript before solving the Four Sum Problem?

easy

A. nums.sort()

B. nums.sort((a, b) => b - a)

C. nums.sorted()

D. nums.sort((a, b) => a - b)

Solution

1. Step 1: Understand JavaScript sort behavior

   By default, nums.sort() sorts elements as strings, which can give wrong order for numbers.

2. Step 2: Use numeric comparison function

   Using nums.sort((a, b) => a - b) sorts numbers in ascending order correctly, which is needed for the Four Sum algorithm.

3. Final Answer:

   nums.sort((a, b) => a - b) -> Option D

4. Quick Check:

   Numeric ascending sort = nums.sort((a, b) => a - b) [OK]

Hint: Use numeric compare function for sorting numbers [OK]

Common Mistakes:

• Using default sort without compare function
• Using descending order when ascending is needed
• Using non-existent method like sorted()

3. What will be the output of the following code snippet?

const nums = [1, 0, -1, 0, -2, 2];
const target = 0;
// Assume findFourSum returns all unique quadruplets summing to target
const result = findFourSum(nums, target);
console.log(result);

Given findFourSum correctly implements the Four Sum algorithm, what is the expected output?

medium

A. [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

B. [[1, 0, -1, 0], [-2, 2, 0, 0]]

C. [[-2, -1, 0, 1], [-1, 0, 0, 1]]

D. [[0, 0, 0, 0]]

Solution

1. Step 1: Sort the array and find quadruplets

   Sorted array is [-2, -1, 0, 0, 1, 2]. The unique quadruplets summing to 0 are [-2, -1, 1, 2], [-2, 0, 0, 2], and [-1, 0, 0, 1].

2. Step 2: Verify quadruplets sum to target

   Each quadruplet sums to 0, matching the target, and all are unique sets.

3. Final Answer:

   [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]] -> Option A

4. Quick Check:

   Unique quadruplets summing to 0 = [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]] [OK]

Hint: Sort array first, then find quadruplets summing to target [OK]

Common Mistakes:

• Not sorting array before processing
• Including duplicate quadruplets
• Incorrect quadruplet sums

4. Identify the error in the following snippet for solving the Four Sum Problem:

function fourSum(nums, target) {
  nums.sort();
  const quadruplets = [];
  for (let i = 0; i < nums.length - 3; i++) {
    for (let j = i + 1; j < nums.length - 2; j++) {
      let left = j + 1;
      let right = nums.length - 1;
      while (left < right) {
        const sum = nums[i] + nums[j] + nums[left] + nums[right];
        if (sum === target) {
          quadruplets.push([nums[i], nums[j], nums[left], nums[right]]);
          left++;
          right--;
        } else if (sum < target) {
          left++;
        } else {
          right--;
        }
      }
    }
  }
  return quadruplets;
}

medium

A. The loops do not cover all indices correctly

B. The array is not sorted numerically before processing

C. The quadruplets array is not returned

D. The sum calculation is incorrect

Solution

1. Step 1: Check sorting method

   The code uses nums.sort() without a compare function, which sorts elements as strings, causing incorrect order for numbers.

2. Step 2: Impact on algorithm correctness

   Incorrect sorting leads to wrong quadruplets or missed solutions because the two-pointer approach depends on sorted numeric order.

3. Final Answer:

   The array is not sorted numerically before processing -> Option B

4. Quick Check:

   Missing numeric sort compare function = The array is not sorted numerically before processing [OK]

Hint: Always use numeric compare in sort for number arrays [OK]

Common Mistakes:

• Using default sort without compare function
• Not returning the result array
• Incorrect loop ranges (not here though)
• Wrong sum calculation (correct here)

5. Given an array nums = [2, 2, 2, 2, 2] and target = 8, what is the correct output of the Four Sum Problem algorithm that finds all unique quadruplets?

hard

A. [[2, 2, 2]]

B. [[2, 2, 2, 2], [2, 2, 2, 2]]

C. [[2, 2, 2, 2]]

D. []

Solution

1. Step 1: Understand the input and target

   All elements are 2, and target is 8. Four 2's sum to 8 exactly.

2. Step 2: Identify unique quadruplets

   Even though there are multiple 2's, only one unique quadruplet [2, 2, 2, 2] exists that sums to 8.

3. Final Answer:

   [[2, 2, 2, 2]] -> Option C

4. Quick Check:

   Unique quadruplet summing to 8 = [[2, 2, 2, 2]] [OK]

Hint: Duplicates form one unique quadruplet if sum matches target [OK]

Common Mistakes:

• Listing duplicate quadruplets multiple times
• Returning empty when quadruplet exists
• Confusing triplets with quadruplets