Three Sum Problem All Unique Triplets in DSA Rust

Mental Model

Find three numbers in a list that add up to zero without repeating the same triplet.

Analogy: Imagine you have a group of friends with different money amounts. You want to find three friends whose combined money is exactly zero, like balancing a small group budget perfectly.

nums: [-4, -1, -1, 0, 1, 2]
indexes: [0]  [1]  [2] [3] [4] [5]
          ↑
          start pointer
                    ↑
                    mid pointer
                          ↑
                          end pointer

Dry Run Walkthrough

Input: nums = [-1, 0, 1, 2, -1, -4]

Goal: Find all unique triplets that sum to zero

Step 1: Sort the array to make it easier to find triplets

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

Why: Sorting helps us use two pointers to find pairs that sum to a target efficiently

Step 2: Fix first element at index 0 (-4), set left=1, right=5

[-4, -1, -1, 0, 1, 2]
first = -4, left = -1, right = 2

Why: We try to find two numbers that sum to 4 (because -4 + x + y = 0 means x + y = 4)

Step 3: Sum = -4 + (-1) + 2 = -3, less than 0, move left pointer right

[-4, -1, -1, 0, 1, 2]
first = -4, left = -1 (index 2), right = 2

Why: Sum too small, increase sum by moving left pointer right

Step 4: Sum = -4 + (-1) + 2 = -3 again, move left pointer right

[-4, -1, -1, 0, 1, 2]
first = -4, left = 0 (index 3), right = 2

Why: Still too small, move left pointer right

Step 5: Sum = -4 + 0 + 2 = -2, move left pointer right

[-4, -1, -1, 0, 1, 2]
first = -4, left = 1 (index 4), right = 2

Why: Sum still less than zero, move left pointer right

Step 6: Sum = -4 + 1 + 2 = -1, move left pointer right

[-4, -1, -1, 0, 1, 2]
first = -4, left = 2 (index 5), right = 2

Why: Left pointer meets right, no triplet with first = -4

Step 7: Fix first element at index 1 (-1), set left=2, right=5

[-4, -1, -1, 0, 1, 2]
first = -1, left = -1, right = 2

Why: Try to find pairs that sum to 1 (because -1 + x + y = 0 means x + y = 1)

Step 8: Sum = -1 + (-1) + 2 = 0, found triplet [-1, -1, 2], move left and right pointers

[-4, -1, -1, 0, 1, 2]
triplets = [[-1, -1, 2]]
left = 3 (0), right = 4 (1)

Why: Sum zero means valid triplet, move pointers to find other triplets

Step 9: Sum = -1 + 0 + 1 = 0, found triplet [-1, 0, 1], move left and right pointers

[-4, -1, -1, 0, 1, 2]
triplets = [[-1, -1, 2], [-1, 0, 1]]
left = 4, right = 3

Why: Sum zero again, add triplet and move pointers

Step 10: Left pointer crossed right, move first pointer to index 2 (-1) but skip duplicate

[-4, -1, -1, 0, 1, 2]
first = -1 (index 2) skipped

Why: Avoid duplicate triplets by skipping same first element

Step 11: Fix first element at index 3 (0), set left=4, right=5

[-4, -1, -1, 0, 1, 2]
first = 0, left = 4, right = 5

Why: Try to find pairs that sum to 0 (0 + x + y = 0 means x + y = 0)

Step 12: Sum = 0 + 1 + 2 = 3, sum too big, move right pointer left

[-4, -1, -1, 0, 1, 2]
first = 0, left = 4, right = 4

Why: Sum too large, decrease sum by moving right pointer left

Step 13: Left pointer crossed right, stop

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

Why: No more pairs to check with first = 0

Result:

[-1, -1, 2] -> [-1, 0, 1] -> null

Annotated Code

DSA Rust

fn three_sum(nums: Vec<i32>) -> Vec<Vec<i32>> {
    let mut nums = nums;
    nums.sort();
    let mut result = Vec::new();
    let n = nums.len();
    for i in 0..n {
        if i > 0 && nums[i] == nums[i - 1] {
            continue; // skip duplicate first elements
        }
        let mut left = i + 1;
        let mut right = n - 1;
        while left < right {
            let sum = nums[i] + nums[left] + nums[right];
            if sum == 0 {
                result.push(vec![nums[i], nums[left], nums[right]]);
                left += 1;
                right -= 1;
                while left < right && nums[left] == nums[left - 1] {
                    left += 1; // skip duplicates
                }
                while left < right && nums[right] == nums[right + 1] {
                    right -= 1; // skip duplicates
                }
            } else if sum < 0 {
                left += 1; // increase sum
            } else {
                right -= 1; // decrease sum
            }
        }
    }
    result
}

fn main() {
    let nums = vec![-1, 0, 1, 2, -1, -4];
    let triplets = three_sum(nums);
    for triplet in triplets {
        println!("{} -> {} -> {} -> null", triplet[0], triplet[1], triplet[2]);
    }
}

nums.sort();

sort the array to enable two-pointer technique

if i > 0 && nums[i] == nums[i - 1] { continue; }

skip duplicate first elements to avoid repeated triplets

while left < right {

iterate with two pointers to find pairs summing to target

let sum = nums[i] + nums[left] + nums[right];

calculate current triplet sum

if sum == 0 { result.push(vec![nums[i], nums[left], nums[right]]);

found valid triplet, add to result

left += 1; right -= 1;

move pointers inward to find new pairs

while left < right && nums[left] == nums[left - 1] { left += 1; }

skip duplicates on left pointer

while left < right && nums[right] == nums[right + 1] { right -= 1; }

skip duplicates on right pointer

else if sum < 0 { left += 1; }

sum too small, increase left pointer to increase sum

else { right -= 1; }

sum too large, decrease right pointer to decrease sum

Output

-1 -> -1 -> 2 -> null

-1 -> 0 -> 1 -> null

Complexity Analysis

Time: O(n^2) because we sort once O(n log n) and then use two nested loops with two pointers scanning the array

Space: O(k) where k is the number of found triplets stored in the output

vs Alternative: Better than naive O(n^3) approach that checks all triplets by brute force

Edge Cases

empty array

returns empty list, no triplets found

DSA Rust

for i in 0..n {

array with less than 3 elements

returns empty list, not enough elements to form triplets

DSA Rust

for i in 0..n {

array with all zeros

returns one triplet [0, 0, 0] without duplicates

DSA Rust

while left < right && nums[left] == nums[left - 1] { left += 1; }

When to Use This Pattern

When asked to find triplets summing to zero or a target with unique results, use sorting plus two pointers to efficiently find pairs complementing a fixed element.

Common Mistakes

Mistake: Not sorting the array before applying two pointers
Fix: Sort the array first to enable the two-pointer technique

Mistake: Not skipping duplicate elements leading to repeated triplets
Fix: Skip duplicates for the first element and after finding a triplet by moving pointers past equal values

Mistake: Moving pointers incorrectly causing infinite loops or missed triplets
Fix: Move left pointer right when sum is too small, right pointer left when sum is too large, and both inward when sum is zero

Summary

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

Use when you need to find combinations of three numbers meeting a sum condition without duplicates.

Sort the array and use a fixed element plus two pointers to efficiently find pairs complementing it.

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