Four Sum Problem All Unique Quadruplets in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to sort the input array before processing.

DSA Typescript

nums.[1]();

Drag options to blanks, or click blank then click option'

Apush

Breverse

Csort

Dpop

Attempts:

3 left

💡 Hint

Common Mistakes

Using reverse instead of sort

Forgetting to sort the array

Sorting the array helps to efficiently find quadruplets and avoid duplicates.

2fill in blank

medium

Complete the code to skip duplicate elements for the first pointer i.

DSA Typescript

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

Drag options to blanks, or click blank then click option'

Ai - 1

Bi + 1

C0

Dnums.length - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using i + 1 instead of i - 1

Not checking for duplicates

We skip the current element if it is the same as the previous one to avoid duplicate quadruplets.

3fill in blank

hard

Fix the error in the while loop condition to move the left pointer correctly.

DSA Typescript

while (left < right && nums[left] === nums[[1]]) left++;

Drag options to blanks, or click blank then click option'

Aright - 1

Bleft + 1

Cright

Dleft - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with left + 1 causes index error

Comparing with right pointer

We compare nums[left] with the previous left element (left - 1) to skip duplicates after moving left pointer.

4fill in blank

hard

Fill both blanks to correctly move the right pointer and skip duplicates.

DSA Typescript

while (left < right && nums[right] === nums[[1]]) [2];

Drag options to blanks, or click blank then click option'

Aright + 1

Bright - 1

Cleft++

Dright--

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with right - 1 instead of right + 1

Incrementing right pointer instead of decrementing

We compare nums[right] with nums[right + 1] (the previously used right position) to skip duplicates and decrement right pointer.

5fill in blank

hard

Fill all three blanks to add the quadruplet to result and move both pointers.

DSA Typescript

result.push([nums[[1]], nums[[2]], nums[left], nums[right]]);
left[3];
right--;

Drag options to blanks, or click blank then click option'

Ai

Bj

C++

D--

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong indices for quadruplet

Decrementing left pointer instead of incrementing

We add quadruplet using indices i and j, then increment left pointer and decrement right pointer to continue searching.

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