Three Sum Problem All Unique Triplets in DSA Rust - Time & Space Complexity

Time Complexity: Three Sum Problem All Unique Triplets

O(n²)

Understanding Time Complexity

We want to understand how the time needed grows when finding all unique triplets that sum to zero in a list.

How does the number of steps change as the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

This code finds all unique triplets in the list that add up to zero by sorting and using two pointers.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Outer loop over each element and inner while loop moving two pointers.
• How many times: Outer loop runs n times; inner loop moves pointers across the remaining elements, roughly n times total per outer loop.

How Execution Grows With Input

As the list size grows, the outer loop grows linearly, and for each outer step, the inner pointer loop also grows linearly.

Input Size (n)	Approx. Operations
10	About 100 steps
100	About 10,000 steps
1000	About 1,000,000 steps

Pattern observation: The steps grow roughly with the square of the input size.

Final Time Complexity

Time Complexity: O(n²)

This means if the list doubles in size, the time to find all triplets roughly quadruples.

Common Mistake

[X] Wrong: "Because there are three numbers, the time complexity must be O(n³)."

[OK] Correct: The sorting and two-pointer method reduce the inner search to linear time per outer loop, so it is O(n²), not cubic.

Interview Connect

Understanding this time complexity helps you explain efficient solutions clearly and shows you can optimize nested loops smartly.

Self-Check

"What if we used three nested loops instead of sorting and two pointers? How would the time complexity change?"

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