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

Concept Flow - Four Sum Problem All Unique Quadruplets

Sort the array

↓

Fix first element i

↓

Fix second element j

↓

Set left = j+1, right = end

↓

While left < right

↓

Sum == target?

↓

Add quadruplet

↓

Skip duplicates

↓

Move pointers

↓

Repeat until all quadruplets found

↓

Return all unique quadruplets

The flow sorts the array, then uses two nested loops to fix the first two elements. Two pointers scan the rest to find quadruplets summing to target, skipping duplicates.

Execution Sample

DSA C

int* fourSum(int* nums, int numsSize, int target, int* returnSize) {
  // Sort nums
  // Loop i from 0 to numsSize-4
  // Loop j from i+1 to numsSize-3
  // Use left and right pointers
  // Find quadruplets summing to target
}

This code finds all unique quadruplets in nums that sum to target.

Execution Table

Step	Operation	i, j, left, right	Sum	Quadruplet Found	Visual State
1	Sort array	-	-	-	[1, 0, -1, 0, -2, 2] → [-2, -1, 0, 0, 1, 2]
2	Fix i=0	i=0	-	-	i points to -2
3	Fix j=1	i=0, j=1	-	-	j points to -1
4	Set left=2, right=5	i=0, j=1, left=2, right=5	-	-	left=2, right=5
5	Calculate sum	i=0, j=1, left=2, right=5	-2 + -1 + 0 + 2 = -1	No	No quadruplet
6	Sum < target(0), move left	left=3, right=5	-	-	left moves to 3 (index 3)
7	Calculate sum	i=0, j=1, left=3, right=5	-2 + -1 + 0 + 2 = -1	No	No quadruplet
8	Sum < target, move left	left=4, right=5	-	-	left moves to 4 (index 4)
9	Calculate sum	i=0, j=1, left=4, right=5	-2 + -1 + 1 + 2 = 0	Yes	Quadruplet [-2, -1, 1, 2] found
10	Skip duplicates, move left and right	left=5, right=4	-	-	left > right, inner loop ends
11	Increment j=2	i=0, j=2	-	-	j points to 0
12	Set left=3, right=5	i=0, j=2, left=3, right=5	-	-	left=3, right=5
13	Calculate sum	i=0, j=2, left=3, right=5	-2 + 0 + 0 + 2 = 0	Yes	Quadruplet [-2, 0, 0, 2] found
14	Skip duplicates, move left and right	left=4, right=4	-	-	left >= right, inner loop ends
15	Increment j=3	i=0, j=3	-	-	j points to 0 (duplicate)
16	Skip duplicate j, increment j=4	i=0, j=4	-	-	j points to 1
17	Set left=5, right=5	i=0, j=4, left=5, right=5	-	-	left == right, inner loop ends
18	Increment i=1	i=1	-	-	i points to -1
19	Fix j=2	i=1, j=2	-	-	j points to 0
20	Set left=3, right=5	i=1, j=2, left=3, right=5	-	-	left=3, right=5
21	Calculate sum	i=1, j=2, left=3, right=5	-1 + 0 + 0 + 2 = 1	No	No quadruplet
22	Sum > target, move right	left=3, right=4	-	-	right moves to 4 (index 4)
23	Calculate sum	i=1, j=2, left=3, right=4	-1 + 0 + 0 + 1 = 0	Yes	Quadruplet [-1, 0, 0, 1] found
24	Skip duplicates, move left and right	left=4, right=3	-	-	left > right, inner loop ends
25	Increment j=3	i=1, j=3	-	-	j points to 0 (duplicate)
26	Skip duplicate j, increment j=4	i=1, j=4	-	-	j points to 1
27	Set left=5, right=5	i=1, j=4, left=5, right=5	-	-	left == right, inner loop ends
28	Increment i=2	i=2	-	-	i points to 0
29	Fix j=3	i=2, j=3	-	-	j points to 0 (duplicate)
30	Skip duplicate j, increment j=4	i=2, j=4	-	-	j points to 1
31	Set left=5, right=5	i=2, j=4, left=5, right=5	-	-	left == right, inner loop ends
32	Increment i=3	i=3	-	-	i points to 0 (duplicate)
33	Skip duplicate i, increment i=4	i=4	-	-	i points to 1
34	Loop ends as i > numsSize-4	-	-	-	All quadruplets found
35	Return result	-	-	Quadruplets: [-2,-1,1,2], [-2,0,0,2], [-1,0,0,1]	Done

💡 i reaches numsSize-4, no more quadruplets possible

Variable Tracker

Variable	Start	After Step 2	After Step 11	After Step 18	After Step 28	After Step 33	Final
i	-	0	0	1	2	4	4
j	-	-	1	2	4	-	-
left	-	-	2	3	3	-	-
right	-	-	5	5	5	-	-
Quadruplets Found	[]	[[-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]]	[[-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 skip duplicates for i, j, left, and right pointers?

Skipping duplicates prevents adding the same quadruplet multiple times. For example, after finding a quadruplet at step 9, we move left and right pointers past duplicates (step 10) to avoid repeats.

Why do we move left pointer when sum < target and right pointer when sum > target?

Because the array is sorted, increasing left moves to a larger number to increase sum, and decreasing right moves to a smaller number to decrease sum. This is shown in steps 6-8 and 21-22.

Why does the inner while loop stop when left >= right?

When left meets or passes right, all pairs for current i and j are checked. For example, after step 14, left=4 and right=4, so loop ends.

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 [-2, -1, 0, 2]

💡 Hint

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

At which step does the condition left >= right first occur, ending the inner loop?

A Step 10

B Step 14

C Step 24

D Step 27

💡 Hint

Look for when 'left' and 'right' pointers meet or cross in the execution table.

If the array was not sorted at step 1, how would the execution table change?

A Sum comparisons would be invalid, and duplicates might not be skipped correctly.

B The quadruplets found would be the same but in different order.

C The pointers left and right would not move.

D The loops for i and j would not run.

💡 Hint

Sorting is essential for correct sum checks and skipping duplicates, as shown in step 1.

Concept Snapshot

Four Sum Problem:
- Sort array first
- Use two nested loops to fix first two elements
- Use two pointers (left, right) to find pairs
- Move pointers based on sum vs target
- Skip duplicates for unique quadruplets
- Return all found quadruplets

Full Transcript

This visualization shows how to find all unique quadruplets in an array that sum to a target. First, the array is sorted. Then, two loops fix the first two elements. Two pointers scan the remaining elements to find pairs that complete the quadruplet. The sum is compared to the target, and pointers move accordingly. Duplicates are skipped to avoid repeated quadruplets. The process continues until all quadruplets are found. The execution table tracks each step, pointer positions, sums, and quadruplets found. Key moments clarify why duplicates are skipped, pointer movements, and loop termination conditions.

Practice

1. What is the main goal of the Four Sum Problem in data structures and algorithms?

easy

A. Find the maximum element in the array

B. Sort the array in ascending order

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

D. Count the number of pairs with a given sum

Solution

1. Step 1: Understand the problem statement

   The Four Sum Problem asks to find four numbers in an array whose sum equals a target value.

2. Step 2: Identify the expected output

   We want all unique sets of four numbers (quadruplets) that add up to the target.

3. Final Answer:

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

4. Quick Check:

   Four Sum = unique quadruplets with target sum [OK]

Hint: Look for four numbers adding to target, not just pairs [OK]

Common Mistakes:

• Confusing with two or three sum problems
• Ignoring uniqueness of quadruplets
• Trying to find maximum or minimum instead of sum

2. Which of the following code snippets correctly initializes the array and target for the Four Sum problem in C?

easy

A. int nums[] = [1, 0, -1, 0, -2, 2]; int target = 0;

B. int nums = {1, 0, -1, 0, -2, 2}; int target = 0;

C. int nums[] = (1, 0, -1, 0, -2, 2); int target = 0;

D. int nums[] = {1, 0, -1, 0, -2, 2}; int target = 0;

Solution

1. Step 1: Check array initialization syntax in C

   Arrays in C are initialized with curly braces {} and square brackets [] for declaration.

2. Step 2: Validate each option

   int nums[] = {1, 0, -1, 0, -2, 2}; int target = 0; uses correct syntax: int nums[] = { ... }; int nums = {1, 0, -1, 0, -2, 2}; int target = 0; misses brackets, C uses parentheses, D uses square brackets incorrectly.

3. Final Answer:

   int nums[] = {1, 0, -1, 0, -2, 2}; int target = 0; -> Option D

4. Quick Check:

   Correct C array syntax = int nums[] = {1, 0, -1, 0, -2, 2}; int target = 0; [OK]

Hint: Use curly braces {} to initialize arrays in C [OK]

Common Mistakes:

• Using parentheses () instead of braces {}
• Missing square brackets [] in declaration
• Using square brackets [] for initialization

3. Given the following C code snippet, what will be the printed output for the quadruplets found?

int nums[] = {1, 0, -1, 0, -2, 2};
int target = 0;
// Assume function fourSum returns all unique quadruplets
// and prints them as quadruplets separated by spaces
// Output format: a b c d\n for each quadruplet
fourSum(nums, 6, target);

medium

A. 1 0 -1 0
-2 2 0 0
-1 1 0 0

B. -2 -1 1 2
-2 0 0 2
-1 0 0 1

C. -2 -1 0 1
-2 0 0 2
-1 0 1 2

D. No quadruplets found

Solution

1. Step 1: Sort the array

   Sorted nums = [-2, -1, 0, 0, 1, 2]

2. Step 2: Find all unique quadruplets summing to 0

   Quadruplets 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 B

4. Quick Check:

   Sum of each quadruplet = 0 [OK]

Hint: Sort array first, then use two pointers for pairs [OK]

Common Mistakes:

• Not sorting array before processing
• Including duplicate quadruplets
• Incorrect sum calculation

4. Identify the bug in the following C code snippet for the Four Sum problem:

void fourSum(int* nums, int numsSize, int target) {
    for (int i = 0; i < numsSize - 3; i++) {
        for (int j = i + 1; j < numsSize - 2; j++) {
            int left = j + 1, right = numsSize - 1;
            while (left < right) {
                int sum = nums[i] + nums[j] + nums[left] + nums[right];
                if (sum == target) {
                    printf("%d %d %d %d\n", 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 repeated outputs

B. Incorrect initialization of left and right pointers

C. Wrong loop ranges causing out-of-bounds access

D. Missing return statement in void function

Solution

1. Step 1: Analyze duplicate handling

   The code prints quadruplets but does not skip duplicates, so repeated quadruplets appear.

2. Step 2: Check other parts

   Left and right pointers are correctly initialized; loop ranges are valid; return statement is not needed in void function.

3. Final Answer:

   No check to skip duplicate quadruplets causing repeated outputs -> Option A

4. Quick Check:

   Duplicates not skipped = No check to skip duplicate quadruplets causing repeated outputs [OK]

Hint: Skip duplicates after finding quadruplets to avoid repeats [OK]

Common Mistakes:

• Not skipping duplicates for i, j, left, right
• Incorrect pointer updates causing infinite loops
• Accessing array out of bounds

5. You are given an array nums = {2, 2, 2, 2, 2} and target 8. How many unique quadruplets sum to the target, and what are they?

hard

A. 1 quadruplet: [2, 2, 2, 2]

B. 5 quadruplets: all combinations of 2's

C. 0 quadruplets: no unique quadruplets

D. 4 quadruplets: different indices but same values

Solution

1. Step 1: Understand array and target

   All elements are 2, target is 8, so quadruplet sum must be 2+2+2+2=8.

2. Step 2: Count unique quadruplets

   Even though multiple indices exist, the quadruplet values are the same, so only one unique quadruplet exists: [2, 2, 2, 2].

3. Final Answer:

   1 quadruplet: [2, 2, 2, 2] -> Option A

4. Quick Check:

   Sum 2+2+2+2=8 unique quadruplet [OK]

Hint: Same values quadruplet counts as one unique quadruplet [OK]

Common Mistakes:

• Counting quadruplets by indices, not unique values
• Assuming multiple quadruplets due to duplicates
• Ignoring uniqueness condition