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

Concept Flow - Four Sum Problem All Unique Quadruplets

Sort the array

↓

Fix first number i

↓

Fix second number j

↓

Set left = j+1, right = end

↓

While left < right

↓

Sum == target?

↓

Add quadruplet

↓

Skip duplicates

↓

Repeat until left >= right

↓

Skip duplicates for j

↓

Repeat for j

↓

Skip duplicates for i

↓

Repeat for i

↓

Return all unique quadruplets

The array is sorted first. Then two nested loops fix the first two numbers. Two pointers move inward to find pairs that sum to the target minus the first two. Duplicates are skipped to ensure unique quadruplets.

Execution Sample

DSA Rust

nums = [1, 0, -1, 0, -2, 2]
target = 0
nums.sort()
for i in 0..nums.len()-3 {
  for j in i+1..nums.len()-2 {
    let mut left = j+1;
    let mut right = nums.len()-1;
    while left < right {
      let sum = nums[i] + nums[j] + nums[left] + nums[right];

This code finds all unique quadruplets in nums that sum to target by sorting and using two nested loops plus two pointers.

Execution Table

Step	Operation	i, j, left, right	Sum	Quadruplet Found	Skip Duplicates	Visual State (Sorted Array)
1	Sort array	-	-	-	-	[-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=0, right=2
5	Calculate sum	0,1,2,5	-2 + -1 + 0 + 2 = -1	-	-	No quadruplet
6	Sum < target, move left	0,1,3,5	-	-	-	left moves to index 3 (0)
7	Calculate sum	0,1,3,5	-2 + -1 + 0 + 2 = -1	-	-	No quadruplet
8	Sum < target, move left	0,1,4,5	-	-	-	left moves to index 4 (1)
9	Calculate sum	0,1,4,5	-2 + -1 + 1 + 2 = 0	[-2, -1, 1, 2]	Skip duplicates if any	Quadruplet found
10	Move left and right	0,1,5,4	-	-	-	left=5, right=4 (left >= right)
11	End while, increment j	i=0, j=2	-	-	-	j points to 0
12	Set left=3, right=5	0,2,3,5	-	-	-	left=0, right=2
13	Calculate sum	0,2,3,5	-2 + 0 + 0 + 2 = 0	[-2, 0, 0, 2]	Skip duplicates if any	Quadruplet found
14	Move left and right	0,2,4,4	-	-	-	left=4, right=4 (left >= right)
15	End while, increment j	i=0, j=3	-	-	Skip duplicate j=3 (0 same as j=2)	Skip duplicate j
16	Increment i	i=1	-	-	-	i points to -1
17	Fix j=2	1,2	-	-	-	j points to 0
18	Set left=3, right=5	1,2,3,5	-	-	-	left=0, right=2
19	Calculate sum	1,2,3,5	-1 + 0 + 0 + 2 = 1	-	-	Sum > target
20	Sum > target, move right	1,2,3,4	-	-	-	right moves to index 4 (1)
21	Calculate sum	1,2,3,4	-1 + 0 + 0 + 1 = 0	[-1, 0, 0, 1]	Skip duplicates if any	Quadruplet found
22	Move left and right	1,2,4,3	-	-	-	left=4, right=3 (left >= right)
23	End while, increment j	1,3	-	-	Skip duplicate j=3 (0 same as j=2)	Skip duplicate j
24	Increment i	i=2	-	-	-	i points to 0
25	End loops	-	-	-	-	All quadruplets found
26	Return result	-	-	-	-	[[-2,-1,1,2], [-2,0,0,2], [-1,0,0,1]]

💡 All i, j combinations checked and left >= right ended inner while loops

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 9	After Step 13	After Step 21	Final
i	-	0	0	0	0	0	1	1
j	-	-	1	1	1	2	2	2
left	-	-	-	2	4	4	4	-
right	-	-	-	5	5	5	4	-
sum	-	-	-	-1	0	0	0	-
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 sum < target instead of moving right?

Because the array is sorted, increasing left moves to a bigger number, increasing the sum to approach the target. This is shown in steps 5-8 where sum < target causes left to move right.

How do we avoid duplicate quadruplets in the result?

We skip duplicate values for i, j, left, and right pointers after finding a quadruplet or when incrementing loops. This is shown in steps 15 and 23 where duplicates for j are skipped.

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

Because left and right pointers cross, meaning all pairs between j and end have been checked. This is shown in steps 10, 14, and 22 where left >= right ends the loop.

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 'Quadruplet Found' column at step 9 in the execution_table.

At which step does the condition left >= right first cause the inner while loop to end?

A Step 10

B Step 14

C Step 22

D Step 26

💡 Hint

Look for the first step where 'left=5, right=4 (left >= right)' appears in the Visual State column.

If the array was not sorted first, how would the execution_table change?

A The sum calculations would be incorrect and duplicates harder to skip.

B The pointers left and right would not move correctly to find pairs.

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

D No change, sorting is optional.

💡 Hint

Refer to the concept_flow where sorting enables two-pointer movement based on sum comparison.

Concept Snapshot

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

Full Transcript

The Four Sum problem finds all unique sets of four numbers in an array that add up to a target. We start by sorting the array to make it easier to find pairs with two pointers. We fix the first two numbers with nested loops. Then, we use two pointers starting after the second fixed number and at the end of the array. We calculate the sum of these four numbers. If the sum equals the target, we add the quadruplet to the result and move both pointers, skipping duplicates. If the sum is less than the target, we move the left pointer right to increase the sum. If the sum is greater, we move the right pointer left to decrease the sum. We repeat this until the pointers cross. We also skip duplicates for the first two fixed numbers to avoid repeated quadruplets. Finally, we return all unique quadruplets found.

Practice

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

easy

A. Count the number of pairs with a given sum

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

C. Find the maximum element in the array

D. Sort the array in ascending order

Solution

1. Step 1: Understand the problem statement

   The Four Sum Problem asks to find all unique groups of four numbers (quadruplets) in an array that add up to a specific target sum.

2. Step 2: Identify the goal

   The goal is not sorting or counting pairs, but specifically finding quadruplets whose sum equals the target.

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 with target sum [OK]

Hint: Look for four numbers adding to target, not sorting or counting [OK]

Common Mistakes:

• Confusing Four Sum with sorting problems
• Looking for pairs instead of quadruplets
• Ignoring uniqueness of quadruplets

2. Which Rust syntax correctly declares a vector of integers named nums?

easy

A. let nums = {1, 2, 3, 4};

B. let nums = [1, 2, 3, 4];

C. let nums = (1, 2, 3, 4);

D. let nums = vec![1, 2, 3, 4];

Solution

1. Step 1: Identify Rust vector syntax

   In Rust, vectors are created using vec![elements] macro, which creates a growable array.

2. Step 2: Check each option

   let nums = vec![1, 2, 3, 4]; uses vec![1, 2, 3, 4] which is correct. let nums = [1, 2, 3, 4]; is an array, not a vector. let nums = (1, 2, 3, 4); is a tuple. let nums = {1, 2, 3, 4}; is invalid syntax.

3. Final Answer:

   let nums = vec![1, 2, 3, 4]; -> Option D

4. Quick Check:

   Vector syntax = vec![...] [OK]

Hint: Use vec! macro for vectors, arrays use brackets only [OK]

Common Mistakes:

• Using array syntax when vector is needed
• Confusing tuples with vectors
• Using curly braces which are invalid here

3. What is the output of the following Rust code snippet that finds quadruplets summing to 0?

let nums = vec![1, 0, -1, 0, -2, 2];
let target = 0;
// Assume function four_sum returns Vec of quadruplets
let result = four_sum(nums, target);
println!("{:?}", result);

Assuming four_sum is correctly implemented, what is the printed output?

medium

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

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

C. [[0, 0, 0, 0]]

D. []

Solution

1. Step 1: Understand the input and target

   The input array is [1, 0, -1, 0, -2, 2] and target sum is 0. We want all unique quadruplets that sum to 0.

2. Step 2: Identify all quadruplets summing to 0

   Possible quadruplets are [-2, -1, 1, 2], [-2, 0, 0, 2], and [-1, 0, 0, 1]. These are unique and sum to 0.

3. Final Answer:

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

4. Quick Check:

   Quadruplets sum to 0 = [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]] [OK]

Hint: Sort array and find quadruplets summing to target [OK]

Common Mistakes:

• Returning incomplete quadruplets
• Ignoring duplicates
• Returning empty list incorrectly

4. Identify the bug in this Rust code snippet for the Four Sum problem:

fn four_sum(nums: Vec<i32>, target: i32) -> Vec {
    let mut nums = nums;
    nums.sort();
    let mut result = Vec::new();
    for i in 0..nums.len() {
        for j in i+1..nums.len() {
            let mut left = j + 1;
            let mut right = nums.len() - 1;
            while left < right {
                let sum = nums[i] + nums[j] + nums[left] + nums[right];
                if sum == target {
                    result.push(vec![nums[i], nums[j], nums[left], nums[right]]);
                    left += 1;
                    right -= 1;
                } else if sum < target {
                    left += 1;
                } else {
                    right -= 1;
                }
            }
        }
    }
    result
}

What is the main issue causing duplicate quadruplets in the result?

medium

A. The vector nums is not sorted before processing

B. The while loop condition left < right is incorrect and should be left <= right

C. The code does not skip duplicate values for i, j, left, and right indices after finding a quadruplet

D. The function does not return the result vector

Solution

1. Step 1: Analyze duplicate handling in loops

   The code finds quadruplets but does not skip over duplicate values for indices i, j, left, and right after adding a quadruplet, causing duplicates in the result.

2. Step 2: Check other options

   The vector is sorted correctly, the while loop condition is correct, and the function returns the result vector properly.

3. Final Answer:

   The code does not skip duplicate values for i, j, left, and right indices after finding a quadruplet -> Option C

4. Quick Check:

   Skipping duplicates needed to avoid repeated quadruplets [OK]

Hint: Skip duplicates after adding quadruplet to avoid repeats [OK]

Common Mistakes:

• Not skipping duplicates for all pointers
• Changing loop conditions incorrectly
• Forgetting to sort the array

5. Given the array nums = [2, 2, 2, 2, 2] and target 8, what is the correct output of a Four Sum function that returns all unique quadruplets summing to the target?

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 contains five 2's and the target sum is 8. We need quadruplets of four numbers summing to 8.

2. Step 2: Identify unique quadruplets

   Only one unique quadruplet exists: [2, 2, 2, 2]. Although multiple combinations exist, duplicates must be avoided.

3. Final Answer:

   [[2, 2, 2, 2]] -> Option A

4. Quick Check:

   Unique quadruplet summing to 8 = [[2, 2, 2, 2]] [OK]

Hint: Avoid duplicates; only one quadruplet of identical numbers [OK]

Common Mistakes:

• Returning duplicate quadruplets multiple times
• Returning empty list incorrectly
• Returning triples instead of quadruplets