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