Four Sum Problem All Unique Quadruplets in DSA C# - Execution Trace

Concept Flow - Four Sum Problem All Unique Quadruplets

Sort the array

↓

Fix first number i

↓

Fix second number j

↓

Use two pointers: left and right

↓

Calculate sum of nums[i

↓

Compare sum with target

↓

left++

↓

Skip duplicates for i, j, left, right

↓

Repeat until all quadruplets found

↓

Return list of unique quadruplets

The flow sorts the array, then uses two nested loops to fix two numbers, and two pointers to find pairs that sum to the target, skipping duplicates to find all unique quadruplets.

Execution Sample

DSA C#

int[] nums = {1, 0, -1, 0, -2, 2};
int target = 0;
var result = FourSum(nums, target);
// Prints all unique quadruplets that sum to 0

This code finds all unique sets of four numbers in the array that add up to the target 0.

Execution Table

Step	Operation	Indices (i,j,left,right)	Sum	Action	Quadruplets Found	Visual State
1	Sort array	-	-	-	[]	[-2, -1, 0, 0, 1, 2]
2	Fix i	i=0	-	-	[]	[-2, -1, 0, 0, 1, 2]
3	Fix j	i=0, j=1	-	-	[]	[-2, -1, 0, 0, 1, 2]
4	Set pointers	i=0, j=1, left=2, right=5	-	-	[]	[-2, -1, 0, 0, 1, 2]
5	Calculate sum	0,1,2,5	-2 + -1 + 0 + 2 = -1	< target	[]	[-2, -1, 0, 0, 1, 2]
6	Move left pointer	0,1,3,5	-	-	[]	[-2, -1, 0, 0, 1, 2]
7	Calculate sum	0,1,3,5	-2 + -1 + 0 + 2 = -1	< target	[]	[-2, -1, 0, 0, 1, 2]
8	Move left pointer	0,1,4,5	-	-	[]	[-2, -1, 0, 0, 1, 2]
9	Calculate sum	0,1,4,5	-2 + -1 + 1 + 2 = 0	== target	[[-2, -1, 1, 2]]	[-2, -1, 0, 0, 1, 2]
10	Skip duplicates left/right	0,1,5,4	-	-	[[-2, -1, 1, 2]]	[-2, -1, 0, 0, 1, 2]
11	Move j	i=0, j=2	-	-	[[-2, -1, 1, 2]]	[-2, -1, 0, 0, 1, 2]
12	Set pointers	0,2,3,5	-	-	[[-2, -1, 1, 2]]	[-2, -1, 0, 0, 1, 2]
13	Calculate sum	0,2,3,5	-2 + 0 + 0 + 2 = 0	== target	[[-2, -1, 1, 2], [-2, 0, 0, 2]]	[-2, -1, 0, 0, 1, 2]
14	Skip duplicates left/right	0,2,4,4	-	-	[[-2, -1, 1, 2], [-2, 0, 0, 2]]	[-2, -1, 0, 0, 1, 2]
15	Move j	i=0, j=3	-	-	[[-2, -1, 1, 2], [-2, 0, 0, 2]]	[-2, -1, 0, 0, 1, 2]
16	Set pointers	0,3,4,5	-	-	[[-2, -1, 1, 2], [-2, 0, 0, 2]]	[-2, -1, 0, 0, 1, 2]
17	Calculate sum	0,3,4,5	-2 + 0 + 1 + 2 = 1	> target	[[-2, -1, 1, 2], [-2, 0, 0, 2]]	[-2, -1, 0, 0, 1, 2]
18	Move right pointer	0,3,4,4	-	-	[[-2, -1, 1, 2], [-2, 0, 0, 2]]	[-2, -1, 0, 0, 1, 2]
19	Move i	i=1	-	-	[[-2, -1, 1, 2], [-2, 0, 0, 2]]	[-2, -1, 0, 0, 1, 2]
20	Fix j	i=1, j=2	-	-	[[-2, -1, 1, 2], [-2, 0, 0, 2]]	[-2, -1, 0, 0, 1, 2]
21	Set pointers	1,2,3,5	-	-	[[-2, -1, 1, 2], [-2, 0, 0, 2]]	[-2, -1, 0, 0, 1, 2]
22	Calculate sum	1,2,3,5	-1 + 0 + 0 + 2 = 1	> target	[[-2, -1, 1, 2], [-2, 0, 0, 2]]	[-2, -1, 0, 0, 1, 2]
23	Move right pointer	1,2,3,4	-	-	[[-2, -1, 1, 2], [-2, 0, 0, 2]]	[-2, -1, 0, 0, 1, 2]
24	Calculate sum	1,2,3,4	-1 + 0 + 0 + 1 = 0	== target	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]	[-2, -1, 0, 0, 1, 2]
25	Skip duplicates left/right	1,2,4,3	-	-	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]	[-2, -1, 0, 0, 1, 2]
26	Move j	1,3	-	-	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]	[-2, -1, 0, 0, 1, 2]
27	Set pointers	1,3,4,5	-	-	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]	[-2, -1, 0, 0, 1, 2]
28	Calculate sum	1,3,4,5	-1 + 0 + 1 + 2 = 2	> target	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]	[-2, -1, 0, 0, 1, 2]
29	Move right pointer	1,3,4,4	-	-	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]	[-2, -1, 0, 0, 1, 2]
30	Move i	i=2	-	-	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]	[-2, -1, 0, 0, 1, 2]
31	Fix j	2,3	-	-	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]	[-2, -1, 0, 0, 1, 2]
32	Set pointers	2,3,4,5	-	-	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]	[-2, -1, 0, 0, 1, 2]
33	Calculate sum	2,3,4,5	0 + 0 + 1 + 2 = 3	> target	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]	[-2, -1, 0, 0, 1, 2]
34	Move right pointer	2,3,4,4	-	-	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]	[-2, -1, 0, 0, 1, 2]
35	End loops	-	-	-	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]	Final result
36	Return result	-	-	-	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]	Done

💡 All quadruplets found and loops exhausted

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 9	After Step 13	After Step 24	Final
i	-	0	0	0	0	1	2
j	-	-	1	1	2	2	3
left	-	-	-	4	3	3	4
right	-	-	-	5	5	4	5
Quadruplets	[]	[]	[]	[[-2, -1, 1, 2]]	[[-2, -1, 1, 2], [-2, 0, 0, 2]]	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]	[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

Key Moments - 3 Insights

Why do we move the left pointer when the sum is less than the target?

Because the array is sorted, moving left pointer to the right increases the sum. This is shown in steps 5-8 where sum < target and left moves forward.

How do we avoid duplicate quadruplets?

We skip duplicate values for i, j, left, and right after finding a quadruplet or moving pointers, as seen in steps 10 and 14 where pointers skip duplicates.

Why do we fix two numbers (i and j) before using two pointers?

Fixing i and j reduces the problem to finding two numbers with a specific sum using two pointers, simplifying the search. This is the main loop structure shown in steps 2-4.

Visual Quiz - 3 Questions

Look at the execution table at step 9. What quadruplet was found?

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

B [-2, 0, 0, 2]

C [-1, 0, 0, 1]

D [0, 0, 1, 2]

💡 Hint

Check the 'Quadruplets Found' column at step 9 in the execution table.

At which step does the sum first equal the target?

A Step 5

B Step 9

C Step 17

D Step 24

💡 Hint

Look for the first '== target' sum in the 'Action' column of the execution table.

If the array was not sorted, how would the two-pointer approach be affected?

A It would still work the same

B We could not reliably move pointers to increase or decrease sum

C We would find duplicates more easily

D The quadruplets would be sorted automatically

💡 Hint

Refer to the concept flow and key moments about why sorting is needed before two-pointer usage.

Concept Snapshot

Four Sum Problem:
- Sort array first
- Use two nested loops to fix first two numbers
- Use two pointers (left, right) to find pairs summing to target
- Move pointers based on sum comparison
- Skip duplicates to ensure unique quadruplets
- Return list of all unique quadruplets

Full Transcript

The Four Sum problem finds all unique sets of four numbers in an array that add up to a target sum. First, the array is sorted to allow efficient searching. Then, two nested loops fix the first two numbers. For the remaining two numbers, two pointers are used: one starting just after the second fixed number, and the other at the end of the array. The sum of these four numbers is compared to the target. If the sum is less, the left pointer moves right to increase the sum. If the sum is more, the right pointer moves left to decrease the sum. If the sum equals the target, the quadruplet is recorded, and pointers move while skipping duplicates to avoid repeated quadruplets. This process continues until all quadruplets are found. The final result is a list of unique quadruplets that sum to the target.

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