Problem statement

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.
Link to problem

Example 1

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

Example 2

Input: nums = []
Output: []

Example 3

Input: nums = [0]
Output: []

Solutions

Approach 1: Brute Force

Essentially what we did in two sum, we run three loops and add our desired numbers into a vector, and also check if the vector already contains what we have obtained.

Implementation in Rust

fn three_sum(numbers: Vec<i32>) -> Vec<Vec<i32>> {
    let mut sorted_nums = numbers.clone();
    sorted_nums.sort();

    let mut results = vec![];

    for i in 0..sorted_nums.len() {
        for j in (i + 1)..sorted_nums.len() {
            for k in (j + 1)..sorted_nums.len() {
                if (sorted_nums[i] + sorted_nums[j] + sorted_nums[k]) == 0 {
                    let result = vec![sorted_nums[i], sorted_nums[j], sorted_nums[k]];
                    if results.contains(&result) {
                        continue;
                    }
                    results.push(result);
                }
            }
        }
    }

    results
}

Time Complexity: $O(n^3)$ Space Complexity: $O(n)$
Runtime on LeetCode: Time Limit Exceeded


Approach 2: Pointers

As the problem states, you have to pick three numbers that add up to 0.
But what happens when you remove one number from the equation? It becomes two sum problem!

We can use that to our advantage and essentially just run one loop which picks our number and another loop that calculates two sum which yields 0 with our number.

I thought of using previously implemented solution for two sum but went with an entirely different approach to see how efficient pointers were and was quite happy.

Pseudocode

sort the numbers array

begin a loop from 0 to n - 1
    check if current element is same as previous
        if yes then go to next iteration
    
    initialize two pointers
    left = i + 1
    right = n - 1

    while left < right
        compute sum
        if sum < 0
            move left pointer 1 place right
        if sum > 0
            move right pointer 1 place left
        if sum is 0
            add the three elements to results
            move left pointer 1 place right
            check if the current element is same as previous element
                if yes then keep moving the pointer

return results

Implementation in Rust

fn three_sum(numbers: Vec<i32>) -> Vec<Vec<i32>> {
    let mut sorted_nums = numbers.clone();
    sorted_nums.sort();

    let mut results = vec![];

    for i in 0..sorted_nums.len() {
        if i > 0 && sorted_nums[i] == sorted_nums[i - 1] {
            continue;
        }

        let curr_element = sorted_nums[i];
        let mut low = i + 1;
        let mut high = sorted_nums.len() - 1;

        while low < high {
            let sum = curr_element + sorted_nums[low] + sorted_nums[high];

            if sum == 0 {
                results.push([curr_element, sorted_nums[low], sorted_nums[high]].to_vec());
                low = low + 1;

                while sorted_nums[low] == sorted_nums[low - 1] && low < high {
                    low = low + 1;
                }
            } else if sum > 0 {
                high = high - 1;
            } else {
                low = low + 1;
            }
        }
    }

    results
}

Time Complexity: $O(n^2)$
Space Complexity: $O(n)$
Runtime on LeetCode: $30$ms