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

Four Sum Problem All Unique Quadruplets

📖 Scenario: You are working on a shopping app that wants to find all unique groups of four products whose prices add up to a special discount target. This helps the app suggest bundles to customers.

🎯 Goal: Build a TypeScript program that finds all unique quadruplets (groups of four numbers) in an array that sum up to a given target value.

📋 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 nums: number[] and target: number and returns all unique quadruplets as an array of arrays

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

Print the result of calling fourSum(prices, target)

💡 Why This Matters

🌍 Real World

Finding groups of items that meet a specific sum is useful in shopping apps, budgeting tools, and financial analysis.

💼 Career

This problem teaches array manipulation, sorting, and two-pointer techniques commonly asked in software engineering interviews.

1

Create the initial array of prices

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

DSA Typescript

// Create the array prices 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 value

Create a variable called target and set it to 0

DSA Typescript

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

Hint

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

3

Write the fourSum function to find unique quadruplets

Write a function called fourSum that takes parameters nums: number[] and target: number. Inside, sort nums, then use nested loops and two pointers to find all unique quadruplets that sum to target. Return the array of quadruplets.

DSA Typescript

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 two pointers for the last two numbers. Skip duplicates to keep quadruplets unique.

4

Print the result of fourSum with prices and target

Print the result of calling fourSum(prices, target) using console.log

DSA Typescript

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

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  0 && nums[i] === nums[i - 1]) continue;
        for (let j = i + 1; j  i + 1 && nums[j] === nums[j - 1]) continue;
            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;
}

// Print the result of fourSum(prices, target)
// 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. 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