Four Sum Problem All Unique Quadruplets in DSA Typescript

Mental Model

Find four numbers in a list that add up to a target sum without repeating any quadruplets.

Analogy: Imagine you have a group of friends and want to pick four unique people whose combined ages add up to a birthday milestone exactly.

Array: [1, 0, -1, 0, -2, 2]
Indices:  0  1   2  3   4  5
Goal: Find quadruplets that sum to 0

Dry Run Walkthrough

Input: list: [1, 0, -1, 0, -2, 2], target: 0

Goal: Find all unique quadruplets that sum to 0

Step 1: Sort the array to make it easier to find quadruplets

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

Why: Sorting helps skip duplicates and use two-pointer technique efficiently

Step 2: Fix first number at index 0 (-2), then fix second number at index 1 (-1)

First two fixed: [-2, -1], searching pairs in [0, 0, 1, 2]

Why: We fix two numbers and look for two others to complete quadruplet

Step 3: Use two pointers: left at index 2 (0), right at index 5 (2), sum = -2 + -1 + 0 + 2 = -1

Sum -1 < target 0, move left pointer right

Why: Sum too small, need bigger numbers, move left pointer forward

Step 4: Left pointer moves to index 3 (0), sum = -2 + -1 + 0 + 2 = -1 again

Sum still -1 < 0, move left pointer right

Why: Still less than target, continue moving left pointer

Step 5: Left pointer moves to index 4 (1), sum = -2 + -1 + 1 + 2 = 0

Sum equals target, quadruplet found: [-2, -1, 1, 2]

Why: Found one quadruplet, record it and move pointers to find others

Step 6: Move left pointer to 5 and right pointer to 4, pointers cross, end inner loop

No more pairs for fixed first two numbers

Why: All pairs checked for this fixed pair

Step 7: Fix first number at index 0 (-2), second number at index 2 (0), two pointers at 3 (0) and 5 (2)

Sum = -2 + 0 + 0 + 2 = 0, quadruplet found: [-2, 0, 0, 2]

Why: Found another quadruplet, record and move pointers

Step 8: Move left pointer to 4 (1), right pointer to 4 (1), pointers cross, end inner loop

No more pairs for fixed first two numbers

Why: All pairs checked for this fixed pair

Step 9: Fix first number at index 1 (-1), second number at index 2 (0), two pointers at 3 (0) and 5 (2)

Sum = -1 + 0 + 0 + 2 = 1 > 0, move right pointer left

Why: Sum too big, decrease sum by moving right pointer left

Step 10: Right pointer moves to 4 (1), sum = -1 + 0 + 0 + 1 = 0, quadruplet found: [-1, 0, 0, 1]

Quadruplet recorded

Why: Sum matches target, record quadruplet

Step 11: Move left pointer to 4 and right pointer to 3, pointers cross, end inner loop

No more pairs for fixed first two numbers

Why: All pairs checked for this fixed pair

Result:

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

Annotated Code

DSA Typescript

class FourSum {
  static fourSum(nums: number[], target: number): number[][] {
    nums.sort((a, b) => a - b); // sort array
    const quadruplets: number[][] = [];
    const n = nums.length;
    for (let i = 0; i < n - 3; i++) {
      if (i > 0 && nums[i] === nums[i - 1]) continue; // skip duplicates for i
      for (let j = i + 1; j < n - 2; j++) {
        if (j > i + 1 && nums[j] === nums[j - 1]) continue; // skip duplicates for 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]]);
            // skip duplicates for left
            while (left < right && nums[left] === nums[left + 1]) left++;
            // skip duplicates for right
            while (left < right && nums[right] === nums[right - 1]) right--;
            left++;
            right--;
          } else if (sum < target) {
            left++; // increase sum
          } else {
            right--; // decrease sum
          }
        }
      }
    }
    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(", ") + "");
}

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

sort array to enable two-pointer technique and duplicate skipping

if (i > 0 && nums[i] === nums[i - 1]) continue; // skip duplicates for i

skip duplicate first numbers to avoid repeated quadruplets

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

skip duplicate second numbers

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

use two pointers to find pairs that complete quadruplet sum

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

record quadruplet when sum matches target

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: Better than naive O(n^4) which checks all quadruplets; sorting and two-pointer reduce complexity

Edge Cases

Empty array

Returns empty list, no quadruplets

DSA Typescript

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

Array with fewer than 4 elements

Returns empty list, no quadruplets possible

DSA Typescript

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

All elements are the same and sum matches target

Returns one quadruplet without duplicates

DSA Typescript

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-pointer approach to efficiently find all combinations without duplicates.

Common Mistakes

Mistake: Not sorting the array before processing, causing duplicate quadruplets and inefficient search
Fix: Sort the array first to enable skipping duplicates and two-pointer technique

Mistake: Not skipping duplicates for i, j, left, or right pointers, leading to repeated quadruplets
Fix: Add checks to skip duplicates at each pointer position

Mistake: Moving pointers incorrectly after finding a quadruplet, causing infinite loops or missed results
Fix: After recording quadruplet, move both pointers inward and skip duplicates carefully

Summary

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

Use when you need to find quadruplets in an array that sum to a specific value without repeats.

Sort the array and use two nested loops plus two pointers to efficiently find quadruplets and skip duplicates.

Practice

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

easy

A. Sort the array in ascending order

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

C. Find the maximum element in the array

D. Count the number of pairs that sum to a target

Solution

1. Step 1: Understand the problem statement

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

2. Step 2: Identify the goal

   The goal is to return all quadruplets without duplicates that sum to the target value.

3. Final Answer:

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

4. Quick Check:

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

Hint: Look for four numbers adding exactly to target [OK]

Common Mistakes:

• Confusing with two sum or three sum problems
• Ignoring uniqueness of quadruplets
• Trying to find maximum or minimum instead of sum

2. Which of the following TypeScript function signatures correctly represents a function solving the Four Sum Problem?

easy

A. function fourSum(target: number, nums: number[]): void

B. function fourSum(nums: number): number

C. function fourSum(nums: string[], target: string): string[]

D. function fourSum(nums: number[], target: number): number[][]

Solution

1. Step 1: Analyze the function parameters and return type

   The function should take an array of numbers and a target number, and return an array of quadruplets (arrays of numbers).

2. Step 2: Match the correct signature

   function fourSum(nums: number[], target: number): number[][] matches this: input is number array and target number, output is array of number arrays.

3. Final Answer:

   function fourSum(nums: number[], target: number): number[][] -> Option D

4. Quick Check:

   Correct input/output types = function fourSum(nums: number[], target: number): number[][] [OK]

Hint: Look for input array and output array of arrays [OK]

Common Mistakes:

• Wrong parameter order or types
• Returning single number instead of array of quadruplets
• Using string types instead of number

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

const nums = [1, 0, -1, 0, -2, 2];
const target = 0;
console.log(fourSum(nums, target));

function fourSum(nums: number[], target: number): number[][] {
  nums.sort((a, b) => a - b);
  const quadruplets: number[][] = [];
  for (let i = 0; i < nums.length - 3; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    for (let j = i + 1; j < nums.length - 2; j++) {
      if (j > i + 1 && nums[j] === nums[j - 1]) continue;
      let left = j + 1, 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]]);
          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 quadruplets;
}

medium

A. []

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

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

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

Solution

1. Step 1: Sort the array and initialize variables

   The array after sorting is [-2, -1, 0, 0, 1, 2]. We use nested loops and two pointers to find quadruplets summing to 0.

2. Step 2: Find all unique quadruplets summing to target

   By iterating and skipping duplicates, the quadruplets found are [-2, -1, 1, 2], [-2, 0, 0, 2], and [-1, 0, 0, 1].

3. Final Answer:

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

4. Quick Check:

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

Hint: Sort array and use two pointers to find quadruplets [OK]

Common Mistakes:

• Not sorting array before processing
• Not skipping duplicates causing repeated quadruplets
• Incorrect pointer movement leading to missed quadruplets

4. Identify the bug in this TypeScript code snippet for the Four Sum Problem:

function fourSum(nums: number[], target: number): number[][] {
  nums.sort((a, b) => a - b);
  const quadruplets: number[][] = [];
  for (let i = 0; i < nums.length - 3; i++) {
    for (let j = i + 1; j < nums.length - 2; j++) {
      let left = j + 1, 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. Missing checks to skip duplicate elements causing repeated quadruplets

B. Incorrect sorting order of the array

C. Wrong initialization of left and right pointers

D. Returning a single quadruplet instead of all quadruplets

Solution

1. Step 1: Review duplicate handling in loops

   The code does not skip duplicate values for i, j, left, or right indices, which can cause repeated quadruplets in the result.

2. Step 2: Identify missing duplicate checks

   Proper skipping of duplicates after pushing quadruplets and in outer loops is needed to ensure uniqueness.

3. Final Answer:

   Missing checks to skip duplicate elements causing repeated quadruplets -> Option A

4. Quick Check:

   Duplicate skipping missing = Missing checks to skip duplicate elements causing repeated quadruplets [OK]

Hint: Always skip duplicates after finding quadruplets [OK]

Common Mistakes:

• Not skipping duplicates in outer loops
• Not skipping duplicates after pushing quadruplet
• Assuming sorting fixes duplicates automatically

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

hard

A. [[2, 2, 2, 2]]

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

C. []

D. [[2, 2, 2]]

Solution

1. Step 1: Understand the input and target

   The array has five identical elements 2, and the target sum is 8.

2. Step 2: Find unique quadruplets summing to 8

   Only one unique quadruplet [2, 2, 2, 2] sums to 8. Even though elements repeat, quadruplets must be unique sets.

3. Final Answer:

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

4. Quick Check:

   Unique quadruplet with sum 8 = [[2, 2, 2, 2]] [OK]

Hint: Check for unique quadruplets even if elements repeat [OK]

Common Mistakes:

• Returning duplicate quadruplets multiple times
• Returning empty list incorrectly
• Confusing triplets with quadruplets