Four Sum Problem All Unique Quadruplets in DSA Typescript - Deep Dive

Overview - Four Sum Problem All Unique Quadruplets

What is it?

The Four Sum Problem asks us to find all unique groups of four numbers in a list that add up to a specific target number. Each group of four numbers is called a quadruplet. The goal is to list all such quadruplets without repeating any. This problem helps us practice searching and combining numbers efficiently.

Why it matters

Without a method to find these quadruplets, checking every possible group would take too long, especially with big lists. This problem teaches us how to reduce unnecessary work and avoid duplicates, which is important in many real-world tasks like data analysis and searching. Without this, programs would be slow and inefficient.

Where it fits

Before this, you should understand arrays, sorting, and the two-pointer technique. After mastering Four Sum, you can explore more complex problems like k-Sum or learn optimization techniques for large data sets.

Mental Model

Core Idea

Find all unique sets of four numbers that sum to the target by sorting the list and using pointers to efficiently explore combinations without repeats.

Think of it like...

Imagine you have a box of different colored beads and want to pick four beads that together weigh exactly a certain amount. Instead of trying every possible group, you sort the beads by weight and carefully pick combinations, skipping groups that would be too heavy or too light, and avoiding picking the same group twice.

Sorted Array: [a1, a2, a3, ..., an]

Outer loops: i and j pick first two numbers
  ↓
Inner loops: left and right pointers find pairs that sum to (target - a[i] - a[j])

Diagram:

  i -> a[i]
    j -> a[j]
      left -> a[left]
      right -> a[right]

Move pointers based on sum comparison:
  sum < target -> move left right
  sum > target -> move right left
  sum == target -> record quadruplet, skip duplicates

Build-Up - 7 Steps

1

Foundation

Understanding the Problem Setup

Concept: Learn what the Four Sum problem asks and what a quadruplet means.

Given an array of numbers and a target sum, find all unique quadruplets (four numbers) that add up exactly to the target. Each quadruplet should be unique, meaning no repeated groups even if numbers repeat in the array.

Result

Clear understanding of the problem goal and output format.

Understanding the problem clearly is the first step to solving it efficiently and avoiding confusion about duplicates.

2

Foundation

Sorting the Array to Simplify Search

Concept: Sort the array to make it easier to find quadruplets and avoid duplicates.

Sorting arranges numbers in order. This helps us use pointers to find sums quickly and skip repeated numbers to avoid duplicate quadruplets.

Result

Sorted array ready for efficient searching.

Sorting transforms a complex search into a structured process, enabling faster and cleaner solutions.

3

Intermediate

Using Two Loops to Fix First Two Numbers

Concept: Fix the first two numbers of the quadruplet using nested loops to reduce the problem to finding two more numbers.

Use two loops: outer loop picks the first number, inner loop picks the second. For each pair, we look for two other numbers that complete the quadruplet.

Result

Reduced problem to finding pairs that sum to (target - first - second).

Breaking the problem into smaller parts simplifies the search and helps manage complexity.

4

Intermediate

Applying Two-Pointer Technique for Remaining Pair

🤔Before reading on: do you think moving both pointers inward always finds all pairs, or do we need to skip some duplicates? Commit to your answer.

Concept: Use two pointers moving inward to find pairs that sum to the needed value, skipping duplicates to ensure unique quadruplets.

Set left pointer just after second number and right pointer at the end. Move pointers based on sum comparison to target. Skip numbers equal to previous to avoid duplicates.

Result

All unique pairs found efficiently for each fixed pair.

Two-pointer technique reduces time from checking all pairs to linear time per fixed pair, making the solution practical.

5

Intermediate

Skipping Duplicates to Ensure Unique Quadruplets

🤔Before reading on: do you think skipping duplicates only for the last two numbers is enough, or must we skip duplicates for all four positions? Commit to your answer.

Concept: Skip repeated numbers at all four positions to avoid duplicate quadruplets in the result.

After sorting, if the current number is the same as the previous one at any position (i, j, left, right), skip it. This prevents repeated quadruplets.

Result

Result contains only unique quadruplets without repeats.

Careful duplicate skipping is crucial to meet problem requirements and avoid bloated outputs.

6

Advanced

Implementing Complete Four Sum in TypeScript

🤔Before reading on: do you think a recursive k-sum approach is simpler or more complex than nested loops for four sum? Commit to your answer.

Concept: Combine all previous ideas into a complete, runnable TypeScript function that finds all unique quadruplets.

```typescript function fourSum(nums: number[], target: number): number[][] { nums.sort((a, b) => a - b); 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 (let j = i + 1; j < n - 2; j++) { if (j > i + 1 && nums[j] === nums[j - 1]) continue; // skip duplicates 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]]); 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; } // Example usage: const result = fourSum([1, 0, -1, 0, -2, 2], 0); console.log(result); ```

Result

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

Seeing the full code connects all concepts and shows how to implement an efficient, duplicate-free solution.

7

Expert

Optimizing and Extending to k-Sum Problems

🤔Before reading on: do you think the four sum approach can be generalized easily to k-sum? Commit to your answer.

Concept: Generalize the approach to solve k-Sum problems using recursion and pruning to improve performance.

The four sum solution is a special case of k-sum. We can write a recursive function that fixes one number and calls itself for k-1 sum on the remaining array. Sorting and skipping duplicates remain key. Pruning (stopping early when sums are impossible) improves speed.

Result

A flexible method to solve sum problems for any k, not just four.

Understanding this generalization reveals the power and limits of the approach and prepares for more complex challenges.

Under the Hood

The algorithm sorts the array to enable ordered traversal. It uses nested loops to fix the first two numbers, then applies two pointers to find pairs that complete the quadruplet. Skipping duplicates at each step ensures unique results. Internally, this reduces the problem from O(n^4) brute force to roughly O(n^3) by avoiding unnecessary checks and duplicates.

Why designed this way?

Sorting and two-pointer techniques were chosen because they allow linear-time pair searches in sorted arrays. Nested loops fix initial numbers to reduce complexity stepwise. Skipping duplicates prevents redundant work and output. Alternatives like hash maps exist but can be more complex or use more memory.

Input Array (unsorted)
    ↓ sort
Sorted Array: ┌─────────────────────────────┐
              │ a1, a2, a3, ..., an        │
              └─────────────────────────────┘

Nested loops:
  i -> a[i]
    j -> a[j]

Two pointers:
  left -> a[left]
  right -> a[right]

Process:
  ┌─────────────┐
  │ Fix i, j    │
  └─────────────┘
        ↓
  ┌─────────────┐
  │ Move left,  │
  │ right to    │
  │ find pairs  │
  └─────────────┘
        ↓
  ┌─────────────┐
  │ Skip        │
  │ duplicates  │
  └─────────────┘
        ↓
  ┌─────────────┐
  │ Collect     │
  │ quadruplets │
  └─────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does sorting the array guarantee no duplicates in the output without extra checks? Commit yes or no.

Common Belief: Sorting alone removes duplicates from the output.

Reality: Sorting helps identify duplicates but you must explicitly skip repeated numbers during iteration to avoid duplicate quadruplets.

Why it matters: Without skipping duplicates, the output will contain repeated quadruplets, which is incorrect and inefficient.

Quick: Is it enough to only skip duplicates for the last two numbers (left and right pointers)? Commit yes or no.

Common Belief: Skipping duplicates only for the two-pointer part is enough to avoid repeated quadruplets.

Reality: Duplicates must be skipped at all four positions (i, j, left, right) to ensure unique quadruplets.

Why it matters: Failing to skip duplicates early leads to repeated quadruplets and wasted computation.

Quick: Is the brute force O(n^4) approach practical for large arrays? Commit yes or no.

Common Belief: Checking all quadruplets directly is fine for any input size.

Reality: Brute force is too slow for large inputs; optimized methods like sorting and two pointers reduce complexity to O(n^3).

Why it matters: Using brute force on large data causes slow programs and poor user experience.

Quick: Can the four sum problem be solved without sorting? Commit yes or no.

Common Belief: Sorting is optional and not necessary to solve the problem.

Reality: Sorting is essential for efficient two-pointer searching and duplicate skipping.

Why it matters: Without sorting, the algorithm becomes inefficient and complex, making it hard to avoid duplicates.

Expert Zone

1

The order of skipping duplicates matters: skipping too early or late can miss valid quadruplets or cause repeats.

2

Pruning search space by checking minimum and maximum possible sums at each step can drastically improve performance.

3

Using recursion to generalize k-sum problems requires careful base cases and duplicate handling to maintain correctness.

When NOT to use

Avoid this approach when the input size is extremely large and performance is critical; consider hashing-based methods or approximate algorithms. For unsorted data where sorting is costly or forbidden, alternative data structures like hash maps may be better.

Production Patterns

In real systems, four sum logic is used in financial fraud detection (finding suspicious transaction groups), recommendation engines (finding item sets), and in coding interviews to test problem-solving and optimization skills.

Connections

Two Pointer Technique

Builds-on

Mastering two pointers is key to efficiently finding pairs in sorted arrays, which is the core of the four sum solution.

k-Sum Problem

Generalization

Understanding four sum prepares you to solve the more general k-sum problem using recursion and similar techniques.

Combinatorics in Mathematics

Same pattern

Finding unique quadruplets relates to combinations in math, where order doesn't matter and duplicates are avoided, linking algorithmic thinking to mathematical counting.

Common Pitfalls

#1 Not skipping duplicates at all positions leads to repeated quadruplets.

Wrong approach:

for (let i = 0; i < n - 3; i++) {
for (let j = i + 1; j < n - 2; j++) {
let left = j + 1;
let right = n - 1;
while (left < right) {
// no checks to skip duplicates
if (sum === target) {
quadruplets.push([nums[i], nums[j], nums[left], nums[right]]);
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
}

Correct approach:

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;
let right = n - 1;
while (left < 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--;
}
}
}
}

Root cause:

Misunderstanding that sorting alone removes duplicates without explicit skipping.

#2 Using brute force to check all quadruplets causes slow performance.

Wrong approach:

for (let i = 0; i < n - 3; i++) {
for (let j = i + 1; j < n - 2; j++) {
for (let k = j + 1; k < n - 1; k++) {
for (let l = k + 1; l < n; l++) {
if (nums[i] + nums[j] + nums[k] + nums[l] === target) {
quadruplets.push([nums[i], nums[j], nums[k], nums[l]]);
}
}
}
}
}

Correct approach:

Use sorting and two-pointer technique as shown in the full implementation to reduce complexity from O(n^4) to O(n^3).

Root cause:

Not knowing or applying efficient search techniques.

#3 Not sorting the array before searching leads to incorrect results and duplicates.

Wrong approach:

function fourSum(nums, target) {
// no sorting
// proceed with two pointers
}

Correct approach:

Sort the array first: nums.sort((a, b) => a - b); before applying two-pointer search.

Root cause:

Underestimating the importance of sorting for ordered traversal and duplicate handling.

Key Takeaways

Sorting the array is essential to efficiently find quadruplets and skip duplicates.

Fixing the first two numbers with loops and using two pointers for the remaining pair reduces complexity from O(n^4) to O(n^3).

Skipping duplicates at all four positions ensures the output contains only unique quadruplets.

The four sum problem is a special case of the k-sum problem and can be generalized using recursion.

Understanding and applying these techniques prepares you for more complex combination and search problems.

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