Three Sum Problem All Unique Triplets in DSA Rust - Execution Trace

Concept Flow - Three Sum Problem All Unique Triplets

Sort the array

↓

Fix first element i

↓

Set left = i+1, right = end

↓

While left < right

↓

Sum = nums[i

↓

Add triplet

↓

Skip duplicates

↓

Move i to next unique

↓

Repeat until i reaches end

↓

Return all unique triplets

Sort the array, fix one element, then use two pointers to find pairs that sum to the negative of the fixed element, skipping duplicates to find all unique triplets.

Execution Sample

DSA Rust

nums = [-1, 0, 1, 2, -1, -4]
Sort nums -> [-4, -1, -1, 0, 1, 2]
for i in 0..len-2:
  left = i+1
  right = len-1
  while left < right:
    sum = nums[i]+nums[left]+nums[right]

This code finds all unique triplets in the array that sum to zero by sorting and using two pointers.

Execution Table

Step	Operation	i	left	right	Sum	Triplets Found	Pointer Changes	Array State
1	Sort array	-	-	-	-	[]	-	[-4, -1, -1, 0, 1, 2]
2	Fix i at 0	0	1	5	-	[]	-	[-4, -1, -1, 0, 1, 2]
3	Calculate sum	0	1	5	-4 + (-1) + 2 = -3	[]	sum < 0, left++	[-4, -1, -1, 0, 1, 2]
4	Move left to 2	0	2	5	-4 + (-1) + 2 = -3	[]	sum < 0, left++	[-4, -1, -1, 0, 1, 2]
5	Move left to 3	0	3	5	-4 + 0 + 2 = -2	[]	sum < 0, left++	[-4, -1, -1, 0, 1, 2]
6	Move left to 4	0	4	5	-4 + 1 + 2 = -1	[]	sum < 0, left++	[-4, -1, -1, 0, 1, 2]
7	Move left to 5	0	5	5	-	[]	left == right, end inner loop	[-4, -1, -1, 0, 1, 2]
8	Fix i at 1	1	2	5	-	[]	-	[-4, -1, -1, 0, 1, 2]
9	Calculate sum	1	2	5	-1 + (-1) + 2 = 0	[[-1, -1, 2]]	sum == 0, add triplet, left++, right--	[-4, -1, -1, 0, 1, 2]
10	Calculate sum	1	3	4	-1 + 0 + 1 = 0	[[-1, -1, 2], [-1, 0, 1]]	sum == 0, add triplet, left++, right--	[-4, -1, -1, 0, 1, 2]
11	Move left to 4, right to 3	1	4	3	-	[[-1, -1, 2], [-1, 0, 1]]	left >= right, end inner loop	[-4, -1, -1, 0, 1, 2]
12	Fix i at 2 (skip duplicate -1)	2	-	-	-	[[-1, -1, 2], [-1, 0, 1]]	skip i duplicate, i++	[-4, -1, -1, 0, 1, 2]
13	Fix i at 3	3	4	5	-	[[-1, -1, 2], [-1, 0, 1]]	-	[-4, -1, -1, 0, 1, 2]
14	Calculate sum	3	4	5	0 + 1 + 2 = 3	[[-1, -1, 2], [-1, 0, 1]]	sum > 0, right--	[-4, -1, -1, 0, 1, 2]
15	Move right to 4	3	4	4	-	[[-1, -1, 2], [-1, 0, 1]]	left >= right, end inner loop	[-4, -1, -1, 0, 1, 2]
16	Fix i at 4	4	-	-	-	[[-1, -1, 2], [-1, 0, 1]]	i at len-2, end outer loop	[-4, -1, -1, 0, 1, 2]

💡 Outer loop ends when i reaches len-2; all unique triplets found.

Variable Tracker

Variable	Start	After Step 2	After Step 8	After Step 13	Final
i	-	0	1	3	4
left	-	1	2	4	-
right	-	5	5	5	-
Triplets Found	[]	[]	[]	[[-1, -1, 2], [-1, 0, 1]]	[[-1, -1, 2], [-1, 0, 1]]

Key Moments - 3 Insights

Why do we skip duplicate values for i and left pointers?

Skipping duplicates avoids adding the same triplet multiple times. For example, at step 12, i moves from 1 to 2 because nums[2] is the same as nums[1], preventing duplicate triplets as shown in execution_table rows 9-11.

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

Because the array is sorted, increasing left moves to a bigger number to increase sum, and decreasing right moves to a smaller number to decrease sum. This is shown in steps 3-6 and 14.

What stops the inner while loop?

The inner loop stops when left pointer is no longer less than right pointer, as in steps 7 and 15, ensuring all pairs for fixed i are checked.

Visual Quiz - 3 Questions

Look at the execution_table at step 9, what triplet is added?

A [-1, -1, 2]

B [-1, 0, 1]

C [-4, 1, 2]

D [0, 1, 2]

💡 Hint

Check the 'Triplets Found' column at step 9 in execution_table.

At which step does the left pointer move past the right pointer ending the inner loop for i=0?

A Step 5

B Step 7

C Step 10

D Step 15

💡 Hint

Look for when 'left == right' or 'left >= right' in execution_table for i=0.

If the array was not sorted, how would the pointer movement logic change?

A Pointers would still move left++ or right-- based on sum comparison

B We could not rely on pointer movement to find sums efficiently

C We would only move the right pointer

D We would only move the left pointer

💡 Hint

Refer to key_moments about why sorting is needed for pointer logic.

Concept Snapshot

Three Sum Problem:
- Sort array first
- Fix one element i
- Use two pointers left=i+1, right=end
- Move pointers based on sum:
  sum == 0: add triplet, move both skipping duplicates
  sum < 0: move left++
  sum > 0: move right--
- Skip duplicates for i and pointers
- Return all unique triplets

Full Transcript

The Three Sum Problem finds all unique triplets in an array that sum to zero. We start by sorting the array to use a two-pointer approach efficiently. We fix one element at a time and use two pointers to find pairs that sum to the negative of the fixed element. If the sum is zero, we add the triplet and move both pointers skipping duplicates. If the sum is less than zero, we move the left pointer to increase the sum. If the sum is greater than zero, we move the right pointer to decrease the sum. We skip duplicates for the fixed element and pointers to avoid repeated triplets. The process continues until the fixed element reaches the third last element. The final result is a list of all unique triplets that sum to zero.

Practice

1. What is the main goal of the Three Sum Problem All Unique Triplets in data structures and algorithms?

easy

A. Find the maximum element in the array

B. Find all unique triplets in an array that sum to zero

C. Sort the array in ascending order

D. Count the number of pairs that sum to zero

Solution

1. Step 1: Understand the problem statement

   The problem asks to find all unique sets of three numbers in the array whose sum is zero.

2. Step 2: Clarify the output

   The output should be a list of triplets with no duplicates, each summing to zero.

3. Final Answer:

   Find all unique triplets in an array that sum to zero -> Option B

4. Quick Check:

   Three Sum Problem = Find unique triplets summing to zero [OK]

Hint: Look for three numbers adding to zero without duplicates [OK]

Common Mistakes:

• Confusing with pair sum problems
• Ignoring uniqueness of triplets
• Only finding one triplet instead of all

2. Which Rust code snippet correctly initializes a vector to solve the Three Sum problem?

easy

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

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

C. let nums = (1, -1, 0, 2, -2);

D. let nums = vec![1, -1, 0, 2, -2];

Solution

1. Step 1: Identify Rust vector syntax

   In Rust, vectors are created using vec![elements] syntax.

2. Step 2: Check each option

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

3. Final Answer:

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

4. Quick Check:

   Vector initialization uses vec! macro [OK]

Hint: Use vec![] to create vectors in Rust [OK]

Common Mistakes:

• Using array syntax instead of vector
• Using tuple instead of vector
• Invalid braces for initialization

3. What is the output of the following Rust code snippet that finds unique triplets summing to zero?

fn main() {
    let mut nums = vec![-1, 0, 1, 2, -1, -4];
    nums.sort();
    let mut result = Vec::new();
    for i in 0..nums.len() - 2 {
        if i > 0 && nums[i] == nums[i - 1] { continue; }
        let (mut left, mut right) = (i + 1, nums.len() - 1);
        while left < right {
            let sum = nums[i] + nums[left] + nums[right];
            if sum == 0 {
                result.push(vec![nums[i], nums[left], nums[right]]);
                while left < right && nums[left] == nums[left + 1] { left += 1; }
                while left < right && nums[right] == nums[right - 1] { right -= 1; }
                left += 1;
                right -= 1;
            } else if sum < 0 {
                left += 1;
            } else {
                right -= 1;
            }
        }
    }
    println!("{:?}", result);
}

medium

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

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

C. [[0, 0, 0]]

D. []

Solution

1. Step 1: Sort the array

   Sorted array is [-4, -1, -1, 0, 1, 2].

2. Step 2: Find triplets summing to zero

   Triplets found are [-1, -1, 2] and [-1, 0, 1].

3. Final Answer:

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

4. Quick Check:

   Unique triplets summing zero = [[-1,-1,2],[-1,0,1]] [OK]

Hint: Sort array, use two pointers to find triplets [OK]

Common Mistakes:

• Not sorting before two-pointer approach
• Including duplicate triplets
• Incorrect pointer movement

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

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

medium

A. Loop runs beyond valid range causing panic

B. Sorting is done after the loop

C. Missing duplicate skipping after finding a triplet

D. Using immutable vector instead of mutable

Solution

1. Step 1: Check duplicate handling after triplet found

   The code does not skip duplicates for left and right pointers after pushing a triplet.

2. Step 2: Understand impact

   Without skipping duplicates, duplicate triplets may be added to the result.

3. Final Answer:

   Missing duplicate skipping after finding a triplet -> Option C

4. Quick Check:

   Duplicate skipping after triplet push is required [OK]

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

Common Mistakes:

• Not skipping duplicates for left and right pointers
• Incorrect loop range causing panic
• Sorting after loop instead of before

5. Given the input vector vec![0, 0, 0, 0], what is the correct output of a properly implemented Three Sum solution that finds all unique triplets summing to zero?

hard

A. [[0, 0, 0]]

B. [[0, 0, 0], [0, 0, 0]]

C. []

D. [[0, 0]]

Solution

1. Step 1: Analyze input with duplicates

   Input has four zeros, so multiple triplets of zeros exist but are duplicates.

2. Step 2: Unique triplets only

   The solution must return only one unique triplet [0, 0, 0].

3. Final Answer:

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

4. Quick Check:

   Only one unique zero triplet exists [OK]

Hint: Return unique triplets only, even if duplicates exist [OK]

Common Mistakes:

• Returning duplicate triplets multiple times
• Returning empty list incorrectly
• Returning pairs instead of triplets