Four Sum Problem All Unique Quadruplets in DSA Javascript - Build from Scratch

Four Sum Problem All Unique Quadruplets

📖 Scenario: You are working on a shopping app that wants to find all unique combinations of four product prices that add up to a special discount target.This helps the app suggest bundles of four products that together match a customer's budget exactly.

🎯 Goal: Build a program that finds all unique quadruplets (groups of four numbers) in an array that sum up to a given target number.This will help the app find all possible product bundles matching the discount target.

📋 What You'll Learn

Create an array called prices with the exact values: [1, 0, -1, 0, -2, 2]

Create a variable called target and set it to 0

Write a function called fourSum that takes prices and target as parameters and returns all unique quadruplets that sum to target

Use sorting and two-pointer technique inside fourSum to find quadruplets efficiently

Print the result of calling fourSum(prices, target)

💡 Why This Matters

🌍 Real World

Finding product bundles that match a customer's budget exactly helps e-commerce apps suggest attractive deals.

💼 Career

This problem teaches array manipulation, sorting, and two-pointer techniques used in coding interviews and real-world data processing.

1

Create the prices array

Create an array called prices with these exact values: [1, 0, -1, 0, -2, 2]

DSA Javascript

# Create the prices array with the given values
// Your code here

Hint

Use const prices = [1, 0, -1, 0, -2, 2]; to create the array.

2

Set the target sum

Create a variable called target and set it to 0

DSA Javascript

const prices = [1, 0, -1, 0, -2, 2];
// Create the target variable and set it to 0
// Your code here

Hint

Use const target = 0; to set the target sum.

3

Write the fourSum function

Write a function called fourSum that takes prices and target as parameters and returns all unique quadruplets that sum up to target. Use sorting and two-pointer technique inside the function.

DSA Javascript

const prices = [1, 0, -1, 0, -2, 2];
const target = 0;
// Write the fourSum function below
// Your code here

Hint

Sort the array first. Use two nested loops for the first two numbers, then use two pointers for the last two numbers. Skip duplicates to keep quadruplets unique.

4

Print the result

Print the result of calling fourSum(prices, target)

DSA Javascript

const prices = [1, 0, -1, 0, -2, 2];
const target = 0;

function fourSum(prices, target) {
    prices.sort((a, b) => a - b);
    const quadruplets = [];
    const n = prices.length;

    for (let i = 0; i  0 && prices[i] === prices[i - 1]) continue;
        for (let j = i + 1; j  i + 1 && prices[j] === prices[j - 1]) continue;
            let left = j + 1;
            let right = n - 1;
            while (left < right) {
                const sum = prices[i] + prices[j] + prices[left] + prices[right];
                if (sum === target) {
                    quadruplets.push([prices[i], prices[j], prices[left], prices[right]]);
                    while (left < right && prices[left] === prices[left + 1]) left++;
                    while (left < right && prices[right] === prices[right - 1]) right--;
                    left++;
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
    return quadruplets;
}

// Print the result of fourSum
// Your code here

Hint

Use console.log(fourSum(prices, target)); to print the result.

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