Four Sum Problem All Unique Quadruplets in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Four Sum Unique Quadruplets Function

What is the output of the following JavaScript function when called with nums = [1, 0, -1, 0, -2, 2] and target = 0?

DSA Javascript

function fourSum(nums, target) {
  nums.sort((a, b) => a - b);
  const quadruplets = [];
  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;
      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]]);
          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;
}

console.log(fourSum([1, 0, -1, 0, -2, 2], 0));

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

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

C [[-1, -1, 1, 1], [0, 0, 0, 0]]

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

💡 Hint

Sort the array first and use two pointers to find pairs that sum to the target minus the first two numbers.

The function sorts the array and uses nested loops with two pointers to find all unique quadruplets that sum to the target. It skips duplicates to ensure uniqueness.

🧠 Conceptual

intermediate

Number of Unique Quadruplets for Given Input

Given the array nums = [2, 2, 2, 2, 2] and target = 8, how many unique quadruplets does the four sum algorithm find?

A 1

B 5

C 10

D 0

💡 Hint

All elements are the same, so only one unique quadruplet is possible if sum matches target.

Since all elements are 2, the only quadruplet summing to 8 is [2, 2, 2, 2]. The algorithm avoids duplicates, so it returns one unique quadruplet.

🔧 Debug

advanced

Identify the Error in Four Sum Implementation

What error will occur when running this code snippet for four sum?

DSA Javascript

function fourSum(nums, target) {
  nums.sort((a, b) => a - b);
  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]]);
          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;
}

A ReferenceError due to undefined variable

B Infinite loop because left and right pointers may not move correctly

C SyntaxError due to missing semicolons

D No error, code runs correctly

💡 Hint

Check the conditions inside the while loops that skip duplicates.

The inner while loops that skip duplicates do not check if left+1 or right-1 are within array bounds, which can cause left or right pointers to move incorrectly and lead to an infinite loop.

📝 Syntax

advanced

Correct Syntax for Four Sum Filtering Duplicates

Which option correctly skips duplicates in the four sum algorithm inside the nested loops?

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

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

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

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

💡 Hint

Duplicates are skipped by continuing the loop when current equals previous element.

Option A correctly skips duplicates by continuing the loop if the current element equals the previous one. Other options either use wrong comparison, wrong indices, or wrong control flow.

🚀 Application

expert

Maximum Number of Unique Quadruplets

Given an array of 100 distinct integers sorted in ascending order and target = 0, what is the maximum number of unique quadruplets the four sum algorithm can find?

A 0

B Exactly 100

C Approximately 3,921,225

D Approximately 392,122

💡 Hint

Number of unique quadruplets from n distinct elements is n choose 4.

The maximum number of unique quadruplets from 100 distinct elements is the combination of 100 elements taken 4 at a time, which is 100! / (4! * 96!) = 3,921,225.

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