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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Four Sum Unique Quadruplets

What is the output of the following C# code that finds all unique quadruplets summing to target 0?

DSA C#

using System;
using System.Collections.Generic;
using System.Linq;

class Program {
    static IList<IList<int>> FourSum(int[] nums, int target) {
        Array.Sort(nums);
        var res = new List<IList<int>>();
        int n = nums.Length;
        for (int i = 0; i < n - 3; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < n - 2; j++) {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                int left = j + 1, right = n - 1;
                while (left < right) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum == target) {
                        res.Add(new List<int>{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 res;
    }

    static void Main() {
        int[] nums = {1, 0, -1, 0, -2, 2};
        int target = 0;
        var result = FourSum(nums, target);
        foreach (var quad in result) {
            Console.WriteLine(string.Join(", ", quad));
        }
    }
}

A

-2, -1, 1, 2
-2, 0, 0, 2

B

-2, -2, 0, 2
-1, 0, 0, 1

C

-2, -1, 1, 2
-2, 0, 0, 2
-1, 0, 0, 1

D

-1, 0, 0, 1
-2, 0, 0, 2
-2, -1, 1, 2
-1, -1, 1, 1

💡 Hint

Remember the code sorts the array and skips duplicates to avoid repeated quadruplets.

The code sorts the array and uses two nested loops with two pointers to find quadruplets summing to target. It skips duplicates to ensure unique quadruplets. The output lists all unique quadruplets summing to zero.

🧠 Conceptual

intermediate

Understanding Duplicate Skipping in Four Sum

Why does the Four Sum solution skip elements when nums[i] == nums[i - 1] or nums[j] == nums[j - 1]?

A To avoid counting the same quadruplet multiple times by skipping duplicate elements at the same loop level.

B To speed up the algorithm by skipping unnecessary elements that cannot form quadruplets.

C To handle negative numbers differently from positive numbers in the array.

D To ensure the quadruplets are sorted in ascending order before adding to the result.

💡 Hint

Think about how duplicates affect the uniqueness of quadruplets.

Skipping duplicates at the i and j loops prevents generating the same quadruplet multiple times, ensuring all quadruplets in the result are unique.

🔧 Debug

advanced

Identify the Error in Modified Four Sum Code

What error will this modified Four Sum code produce when run?

DSA C#

static IList<IList<int>> FourSum(int[] nums, int target) {
    Array.Sort(nums);
    var res = new List<IList<int>>();
    int n = nums.Length;
    for (int i = 0; i < n - 3; i++) {
        for (int j = i + 1; j < n - 2; j++) {
            int left = j + 1, right = n - 1;
            while (left < right) {
                int sum = nums[i] + nums[j] + nums[left] + nums[right];
                if (sum == target) {
                    res.Add(new List<int>{nums[i], nums[j], nums[left], nums[right]});
                    left++;
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
    return res;
}

A Infinite loop because left and right pointers never move.

B NullReferenceException due to uninitialized list.

C IndexOutOfRangeException when accessing nums[left] or nums[right].

D No error; code runs correctly but may include duplicate quadruplets.

💡 Hint

Check if duplicates are handled and if pointers move correctly.

The code runs without exceptions but does not skip duplicates, so the result may contain repeated quadruplets.

❓ Predict Output

advanced

Output of Four Sum with Negative Target

What is the output of this Four Sum code with target = -1?

DSA C#

int[] nums = {2, 1, 0, -1, -2, -1};
int target = -1;
var result = FourSum(nums, target);
foreach (var quad in result) {
    Console.WriteLine(string.Join(", ", quad));
}

static IList<IList<int>> FourSum(int[] nums, int target) {
    Array.Sort(nums);
    var res = new List<IList<int>>();
    int n = nums.Length;
    for (int i = 0; i < n - 3; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        for (int j = i + 1; j < n - 2; j++) {
            if (j > i + 1 && nums[j] == nums[j - 1]) continue;
            int left = j + 1, right = n - 1;
            while (left < right) {
                int sum = nums[i] + nums[j] + nums[left] + nums[right];
                if (sum == target) {
                    res.Add(new List<int>{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 res;
}

A

-2, -1, 0, 2
-1, -1, 0, 1

B

-2, -1, 0, 0
-2, 0, 0, 1
-1, -1, 0, 1

C

-2, -1, 0, 1
-1, -1, 0, 1

D

-2, -1, 0, 0
-2, -1, 1, 1
-1, -1, 0, 1

💡 Hint

Check the sorted array and carefully find quadruplets summing to -1.

The unique quadruplets summing to -1 are [-2, -1, 0, 2] and [-1, -1, 0, 1].

🚀 Application

expert

Count Unique Quadruplets Summing to Target

Given the array nums = [1, 2, -2, -1, 0, 0, 1] and target = 1, how many unique quadruplets sum to the target?

A 4

B 3

C 2

D 5

💡 Hint

Use the Four Sum approach with duplicate skipping to find all unique quadruplets.

The unique quadruplets summing to 1 are [ -2, 0, 1, 2 ], [ -1, 0, 0, 2 ], and [ -1, 0, 1, 1 ], totaling 3.

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. Count the number of pairs with a given sum

C. Find the maximum element in the array

D. Find all unique quadruplets in an array that sum up to a target value

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 specific target sum.

2. Step 2: Differentiate from other problems

   Unlike sorting or finding maximum, this problem focuses on quadruplets and their sums, not individual elements or pairs.

3. Final Answer:

   Find all unique quadruplets in an array that sum up to a target value -> Option D

4. Quick Check:

   Four Sum Problem = Find quadruplets with target sum [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 C# code snippets correctly initializes a list to store quadruplets for the Four Sum Problem?

easy

A. var quadruplets = new List<List<int>>();

B. var quadruplets = new List<int>();

C. var quadruplets = new Dictionary<int, int>();

D. var quadruplets = new int[4];

Solution

1. Step 1: Identify the data structure for storing quadruplets

   Each quadruplet is a list of 4 integers, so a list of lists is needed to store multiple quadruplets.

2. Step 2: Match with C# syntax

   Using List<List<int>> correctly represents multiple quadruplets, unlike a single list or dictionary.

3. Final Answer:

   var quadruplets = new List<List<int>>(); -> Option A

4. Quick Check:

   Use List of List for quadruplets [OK]

Hint: Use List<List<int>> to store multiple quadruplets [OK]

Common Mistakes:

• Using List<int> for multiple quadruplets
• Using Dictionary instead of List
• Using fixed-size array for dynamic quadruplets

3. For the input array nums = [1, 0, -1, 0, -2, 2] and target 0, what does FourSum(nums, 0) return?
Assuming FourSum returns all unique quadruplets that sum to target.

medium

A. []

B. [[1, 0, -1, 0]]

C. [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

D. [[0, 0, 0, 0]]

Solution

1. Step 1: Sort and find quadruplets summing to 0

   Sorting nums gives [-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 uniqueness and completeness

   All quadruplets are unique and sum exactly to 0, matching the expected output.

3. Final Answer:

   [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]] -> Option C

4. Quick Check:

   Unique quadruplets sum to 0 = [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]] [OK]

Hint: Sort array first, then find quadruplets with two pointers [OK]

Common Mistakes:

• Not sorting array before processing
• Including duplicate quadruplets
• Missing some valid quadruplets

4. Identify the bug in this C# snippet for the Four Sum Problem:

for (int i = 0; i < nums.Length - 3; i++) {
    for (int j = i + 1; j < nums.Length - 2; j++) {
        int left = j + 1, right = nums.Length - 1;
        while (left < right) {
            int sum = nums[i] + nums[j] + nums[left] + nums[right];
            if (sum == target) {
                result.Add(new List<int> { nums[i], nums[j], nums[left], nums[right] });
                left++;
                right--;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
}

medium

A. No check to skip duplicate quadruplets causing duplicates in result

B. Incorrect initialization of left and right pointers

C. Wrong loop ranges for i and j causing index out of range

D. Missing sorting of the input array before processing

Solution

1. Step 1: Analyze duplicate handling

   The code adds quadruplets without skipping duplicates, so repeated quadruplets can appear in the result.

2. Step 2: Check other parts

   Left and right pointers are correctly initialized; loop ranges are valid; sorting is assumed done before this snippet.

3. Final Answer:

   No check to skip duplicate quadruplets causing duplicates in result -> Option A

4. Quick Check:

   Missing duplicate skip = No check to skip duplicate quadruplets causing duplicates in result [OK]

Hint: Always skip duplicates after finding quadruplets [OK]

Common Mistakes:

• Not skipping duplicates for i, j, left, right
• Assuming sorting is done inside the loop
• Incorrect pointer updates causing infinite loops

5. Given the 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?

medium

A. [[2, 2, 2, 2], [2, 2, 2, 2]]

B. [[2, 2, 2, 2]]

C. []

D. [[2, 2, 2]]

Solution

1. Step 1: Understand the input and target

   All elements are 2, and target is 8, so quadruplets of four 2's sum to 8.

2. Step 2: Identify unique quadruplets

   Only one unique quadruplet [2, 2, 2, 2] exists despite duplicates in input.

3. Final Answer:

   [[2, 2, 2, 2]] -> Option B

4. Quick Check:

   Only one unique quadruplet sums to 8 [OK]

Hint: Duplicates form one unique quadruplet if sum matches target [OK]

Common Mistakes:

• Counting duplicate quadruplets multiple times
• Returning empty list when quadruplet exists
• Returning triplets instead of quadruplets