Three Sum Problem All Unique Triplets in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Three Sum Unique Triplets Function

What is the output of the following Rust function when called with input [-1, 0, 1, 2, -1, -4]?

DSA Rust

fn three_sum(nums: Vec<i32>) -> Vec<Vec<i32>> {
    let mut nums = nums;
    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 = i + 1;
        let mut right = 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]]);
                while left + 1 < nums.len() && left < right && nums[left] == nums[left + 1] {
                    left += 1;
                }
                while right > 0 && left < right && nums[right] == nums[right - 1] {
                    right -= 1;
                }
                left += 1;
                right -= 1;
            } else if sum < 0 {
                left += 1;
            } else {
                right -= 1;
            }
        }
    }
    res
}

fn main() {
    let input = vec![-1, 0, 1, 2, -1, -4];
    let result = three_sum(input);
    println!("{:?}", result);
}

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

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

C [[-1, -1, 2], [-1, 0, 1]]

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

💡 Hint

Sort the array first and use two pointers to find pairs that sum with nums[i] to zero.

The function sorts the array and uses a fixed pointer i and two pointers left and right to find triplets that sum to zero. It skips duplicates to ensure unique triplets. For the input [-1, 0, 1, 2, -1, -4], the unique triplets are [-1, -1, 2] and [-1, 0, 1].

🧠 Conceptual

intermediate

Number of Unique Triplets in Three Sum

Given the input array [3, -2, 1, 0, -1, 2, -3], how many unique triplets sum to zero?

A 3

B 5

C 4

D 2

💡 Hint

Try sorting and then find triplets using two pointers.

The unique triplets that sum to zero are [-3,1,2], [-2,0,2], and [-1,0,1]. Other suggested triplets include elements not in the array or duplicates. So total 3 unique triplets.

🔧 Debug

advanced

Identify the Bug in Three Sum Implementation

What error will this Rust code produce when run with input [0, 0, 0, 0]?

DSA Rust

fn three_sum(nums: Vec<i32>) -> Vec<Vec<i32>> {
    let mut nums = nums;
    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 = i + 1;
        let mut right = 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]]);
                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;
            }
        }
    }
    res
}

fn main() {
    let input = vec![0, 0, 0, 0];
    let result = three_sum(input);
    println!("{:?}", result);
}

A No error, outputs [[0, 0, 0]]

B Infinite loop due to left and right pointers not moving

C Compilation error due to mutable borrow

D Index out of bounds panic at nums[left + 1]

💡 Hint

Check the conditions inside the while loops that skip duplicates.

When left is at the second last index, nums[left + 1] accesses out of bounds causing a panic. The condition should ensure left + 1 < nums.len() before accessing nums[left + 1].

📝 Syntax

advanced

Correct Syntax for Skipping Duplicates in Three Sum

Which option correctly fixes the syntax error in this Rust snippet for skipping duplicates? { x: x*2 if x > 2 for x in 0..5 }

A let result = { x: x*2 for x in 0..5 if x > 2 };

B let result = (0..5).filter(|&x| x > 2).map(|x| x * 2).collect::<Vec<_>>();

C let result = (0..5).map(|x| if x > 2 { x * 2 }).collect::<Vec<_>>();

D let result = (0..5).filter(|x| x > 2).map(|x| x * 2);

💡 Hint

Rust uses iterators with filter and map, not Python-style comprehensions.

Option B uses Rust iterator methods filter and map correctly and collects into a vector. Option B is invalid syntax. Option B returns Option due to if without else, causing type mismatch. Option B misses collect(), so result is an iterator, not a vector.

🚀 Application

expert

Optimizing Three Sum for Large Inputs

Which approach best optimizes the Three Sum problem for very large input arrays to reduce time complexity?

A Sort the array and use two pointers for each element to find pairs, achieving O(n^2) time.

B Use three nested loops to check all triplets, achieving O(n^3) time.

C Use a hash set to store complements and check pairs in O(n) time overall.

D Sort the array and use binary search for the third element for each pair, achieving O(n^2 log n) time.

💡 Hint

Consider the best known time complexity for Three Sum and practical approaches.

The optimal known approach sorts the array and uses two pointers for each element, resulting in O(n^2) time. Three nested loops are slower (O(n^3)). Using hash sets for complements is tricky for triplets and usually not better than O(n^2). Binary search adds log n factor, making it slower than two pointers.

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