Four Sum Problem All Unique Quadruplets in DSA Javascript - 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 finding combinations or patterns in data. Without this, programs would be slow and inefficient.

Where it fits

Before this, you should understand arrays, sorting, and the two-pointer technique for simpler sum problems like Two Sum and Three Sum. After mastering Four Sum, you can explore more complex combination problems and optimization techniques in algorithms.

Mental Model

Core Idea

Find all unique sets of four numbers that add up to the target by sorting the list and using nested loops combined with two 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 first sort the beads by weight, then carefully pick beads from the lightest and heaviest ends, moving inward to find the perfect combination without checking the same group twice.

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

Outer loops: i and j pick first two numbers
  ┌─────────────┐
  │ i -> a[i]    │
  │ j -> a[j]    │
  └─────────────┘

Two pointers: left and right find last two numbers
  left -> a[left]       right -> a[right]

Move pointers inward based on sum comparison

Result: Unique quadruplets where a[i] + a[j] + a[left] + a[right] == target

Build-Up - 7 Steps

1

Foundation

Understanding the Problem Setup

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

We have a list of numbers and a target number. We want to find all groups of four numbers from the list that add up exactly to the target. Each group is called a quadruplet. We must avoid listing the same quadruplet more than once, even if the numbers appear multiple times in the list.

Result

Clear understanding of the problem goal and constraints.

Knowing the problem's goal precisely helps avoid confusion and guides how to approach the solution.

2

Foundation

Sorting the Array to Simplify Searching

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

Sorting arranges numbers from smallest to largest. This order helps us use pointers to find sums efficiently 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 Nested Loops for First Two Numbers

🤔Before reading on: Do you think using two loops for the first two numbers is enough to find all quadruplets? Commit to yes or no.

Concept: Pick the first two numbers of the quadruplet using two loops, then find the remaining two numbers with pointers.

We use two loops: the outer loop picks the first number, the inner loop picks the second. For each pair, we look for two more numbers that complete the quadruplet. This breaks the problem into smaller parts.

Result

Pairs of first two numbers selected systematically.

Breaking the problem into choosing two numbers first reduces complexity and sets up for efficient searching of the last two.

4

Intermediate

Applying Two Pointers for Last Two Numbers

🤔Before reading on: Will moving two pointers inward always find all pairs that sum to the needed value? Commit to yes or no.

Concept: Use two pointers starting from both ends of the remaining array segment to find pairs that complete the quadruplet sum.

After choosing first two numbers, set one pointer just after the second number and another at the end of the array. Move pointers inward based on whether the sum is too small or too large, collecting quadruplets when sums match.

Result

All quadruplets with chosen first two numbers found efficiently.

Two pointers exploit the sorted order to find pairs quickly without checking every combination.

5

Intermediate

Skipping Duplicates to Ensure Unique Quadruplets

🤔Before reading on: Do you think skipping duplicates is necessary only for the last two numbers or for all four? Commit to your answer.

Concept: Avoid repeating the same quadruplet by skipping over numbers that are the same as previous ones at every step.

When looping or moving pointers, if the current number is the same as the previous one, skip it. This prevents adding the same quadruplet multiple times.

Result

Only unique quadruplets collected, no repeats.

Skipping duplicates at every step is crucial to meet the problem's requirement of unique quadruplets.

6

Advanced

Optimizing with Early Termination Checks

🤔Before reading on: Can checking sums early reduce unnecessary loops? Commit to yes or no.

Concept: Use the sorted array to stop loops early when sums cannot reach the target, saving time.

Before inner loops or pointer moves, check if the smallest or largest possible sums with current numbers can reach the target. If not, skip or break loops early.

Result

Faster execution by avoiding impossible searches.

Early checks prevent wasted work, making the solution scalable for large inputs.

7

Expert

Handling Edge Cases and Large Inputs Efficiently

🤔Before reading on: Do you think the same approach works well for very large arrays with many duplicates? Commit to yes or no.

Concept: Carefully handle edge cases like empty arrays, very small arrays, and many duplicates to maintain correctness and efficiency.

Check for array length less than 4 early to return empty. Use duplicate skipping strictly. Consider integer overflow in some languages (not in JavaScript). Use early termination aggressively. This ensures the algorithm works well in all scenarios.

Result

Robust and efficient solution that handles all inputs correctly.

Anticipating and handling edge cases prevents bugs and performance issues in real-world use.

Under the Hood

The algorithm first sorts the array to arrange numbers in order. It then uses two nested loops to fix the first two numbers of the quadruplet. For the remaining two numbers, it uses two pointers starting from the ends of the remaining array segment, moving inward to find pairs that sum to the needed value. Duplicate numbers are skipped at every step to avoid repeated quadruplets. Early termination checks use the sorted order to stop searching when sums cannot reach the target, improving efficiency.

Why designed this way?

Sorting and two-pointer techniques reduce the problem's complexity from brute force O(n^4) to roughly O(n^3). Skipping duplicates ensures uniqueness without extra data structures. Early termination leverages sorted order to avoid unnecessary work. Alternatives like hash maps exist but can be more complex or use more memory. This design balances simplicity, speed, and memory use.

Input Array (unsorted)
    ↓ sort
Sorted Array: [a1, a2, ..., an]

Outer loop i -> a[i]
  └─ Inner loop j -> a[j]
       └─ Two pointers left, right
            ┌─────────────┐
            │ sum = a[i]+a[j]+a[left]+a[right]
            │ if sum == target -> record quadruplet
            │ if sum < target -> left++
            │ if sum > target -> right--
            └─────────────┘

Skip duplicates at i, j, left, right

Early termination checks before loops

Result: Unique quadruplets list

Myth Busters - 4 Common Misconceptions

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

Common Belief: Sorting alone removes duplicates from the quadruplets automatically.

Reality: Sorting helps identify duplicates but you must explicitly skip repeated numbers during loops and pointer moves to avoid duplicate quadruplets.

Why it matters: Without skipping duplicates, the output will contain repeated quadruplets, failing the problem's uniqueness requirement.

Quick: Is it enough to use two nested loops and check all pairs for the last two numbers without pointers? Commit to yes or no.

Common Belief: Using two nested loops for all four numbers is fine and simple enough.

Reality: Using four nested loops leads to O(n^4) time, which is very slow. Two pointers reduce this to O(n^3), making the solution practical.

Why it matters: Ignoring two pointers causes inefficient solutions that don't scale to large inputs.

Quick: Can the two-pointer approach be used without sorting the array? Commit to yes or no.

Common Belief: Two pointers work on any array, sorted or not.

Reality: Two pointers require a sorted array to move inward correctly based on sum comparisons.

Why it matters: Using two pointers on unsorted data leads to incorrect results and missed quadruplets.

Quick: Does the algorithm always find quadruplets in ascending order? Commit to yes or no.

Common Belief: The quadruplets are always returned sorted internally and in ascending order.

Reality: Quadruplets are sorted because the array is sorted and pointers move forward, but the order of quadruplets in the output depends on loop order and is not guaranteed sorted globally.

Why it matters: Assuming global order can cause confusion when comparing outputs or testing.

Expert Zone

1

Skipping duplicates must be done carefully at all four indices (i, j, left, right) to avoid subtle repeated quadruplets.

2

Early termination checks can be applied at multiple levels (i, j loops) by comparing minimal and maximal possible sums to the target, greatly improving performance.

3

In JavaScript, integer overflow is not a concern, but in other languages, careful handling of large sums is needed to avoid errors.

When NOT to use

This approach is not ideal when the input size is extremely large and performance is critical; in such cases, approximate or probabilistic methods might be better. Also, if memory is limited and the array is huge, hash-based methods or streaming algorithms could be alternatives.

Production Patterns

In real systems, Four Sum logic is often used in fraud detection, recommendation engines, or pattern matching where combinations of features must meet criteria. Implementations use sorting and two-pointer techniques combined with caching and pruning to handle large datasets efficiently.

Connections

Three Sum Problem

Builds-on

Understanding Three Sum helps grasp Four Sum since Four Sum extends the idea by adding one more fixed number and searching pairs with two pointers.

Two Pointer Technique

Core technique

Mastering two pointers is essential for efficient sum problems; it reduces nested loops and speeds up searching in sorted arrays.

Combinatorics in Mathematics

Conceptual similarity

Finding quadruplets is like choosing combinations of four elements from a set, linking algorithmic search to mathematical combination theory.

Common Pitfalls

#1 Not skipping duplicates leads to repeated quadruplets in output.

Wrong approach:

for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
let left = j + 1, right = n - 1;
while (left < right) {
let sum = nums[i] + nums[j] + nums[left] + nums[right];
if (sum == target) {
result.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; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue;
for (let j = i + 1; j < n; j++) {
if (j > i + 1 && nums[j] === nums[j - 1]) continue;
let left = j + 1, right = n - 1;
while (left < right) {
let 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--;
}
}
}
}

Root cause:

Not understanding that duplicates can appear at any index and must be skipped explicitly to ensure unique quadruplets.

#2 Using four nested loops causes very slow performance.

Wrong approach:

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

Correct approach:

Use two nested loops for i and j, then two pointers left and right to find pairs efficiently, reducing time complexity from O(n^4) to O(n^3).

Root cause:

Not knowing or applying the two-pointer technique to reduce complexity.

#3 Applying two pointers without sorting leads to incorrect results.

Wrong approach:

Use two pointers on unsorted array without sorting first.

Correct approach:

Sort the array first, then apply two pointers to find pairs that sum to the needed value.

Root cause:

Misunderstanding that two pointers rely on sorted order to move pointers correctly.

Key Takeaways

The Four Sum problem finds all unique groups of four numbers that add up to a target by sorting and using nested loops with two pointers.

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

Two pointers reduce the search for pairs from O(n^2) to O(n), making the overall solution O(n^3).

Skipping duplicates at every step ensures the output contains only unique quadruplets.

Early termination checks and careful edge case handling improve performance and robustness.

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