Three Sum Problem All Unique Triplets in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main goal of the Three Sum Problem?

To find all unique triplets in an array that add up to zero.

beginner

Why do we sort the array before solving the Three Sum Problem?

Sorting helps to avoid duplicates easily and allows using two pointers to find pairs efficiently.

intermediate

In the Two Pointer approach for Three Sum, what do the two pointers represent?

They represent the start and end of the remaining array segment to find pairs that sum with the current element to zero.

intermediate

How do you avoid duplicate triplets in the Three Sum solution?

Skip over duplicate elements for the current index and also skip duplicates when moving the two pointers.

intermediate

What is the time complexity of the common Two Pointer solution for the Three Sum Problem?

O(n^2), where n is the number of elements in the array.

What is the first step in solving the Three Sum Problem efficiently?

A Use a hash map

B Sort the array

C Reverse the array

D Split the array into halves

Sorting the array helps to use two pointers and avoid duplicates easily.

In the Two Pointer approach, if the sum of the triplet is less than zero, what should you do?

A Stop the search

B Move the right pointer to the left

C Move the left pointer to the right

D Move both pointers

Moving the left pointer right increases the sum because the array is sorted.

How do you ensure the triplets are unique in the output?

A Skip duplicate elements during iteration

B Add all triplets without checking

C Sort triplets after finding them

D Use a hash set to store triplets

Skipping duplicates during iteration prevents repeated triplets.

What data structure is commonly used to store the final triplets?

A Vector of vectors (list of lists)

B Hash map

C Stack

D Queue

A vector of vectors stores multiple triplets as lists.

What is the overall time complexity of the Two Pointer solution for Three Sum?

A O(n)

B O(n log n)

C O(n^3)

D O(n^2)

Sorting is O(n log n), and the two pointer search is O(n^2), so overall O(n^2).

Explain step-by-step how the Two Pointer technique works to find all unique triplets that sum to zero.

Think about how sorting helps and how two pointers move based on sum.

Describe how to handle duplicates in the Three Sum problem to ensure all triplets are unique.

Duplicates appear because of repeated numbers; skipping them avoids repeated results.

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