Input = [-1, 0, 1, 2, -1, -15, 70], Output: [ [-1, 0, 1], [-1, -1, 2] ]
This problem can be solved in 2 ways:
- Time complexity O (n ^ 3).
- Time complexity O(n^2).
We shall look into both of the solutions now:
Solution 1: Iterative method:
The solution here is simple, we take 3 pointers in 3 for loops, i, j, k.
Where
i starts from base index, j is i + 1 k is j + 1
We recursively check for the value, then list out the values, whose sum is equal to zero.
Let us consider the array [-8, -7, 5, 2]
Pass 0: i = 0, j = 1, k = 2 -8 -7 + 5 = -10 i = 0, j = 1, k = 3 -8 -7 + 2 = -13 i = 0, j = 2, k = 3 -8 + 5 + 2 = -1
Pass 1: i = 1, j = 2, k = 3 -7 + 5 + 2 = 0
We got our solution.
The iterative solution in C++
#include<iostream> #include <vector> using namespace std; vector<vector<int> > threeSumIterativeSolution (vector<int>& input_set) { vector<vector<int> > final_result_set; for (int i = 0; i < input_set.size(); i++) { for(int j = i + 1; j < input_set.size(); j++) { for(int k = i + 2; k < input_set.size(); k++) { if(j == k || i == j || i ==k) { break; } if(input_set[i] + input_set[j] + input_set[k] == 0 && !(j == k || k == i)) // to avoid duplicate elements { // if above condition is true, then save it in intermediate vector. vector<int> current_combination; current_combination.push_back(input_set[i]); current_combination.push_back(input_set[j]); current_combination.push_back(input_set[k]); // then transfer the intermediate vector to final vector final_result_set.push_back(current_combination); } } } } return final_result_set; } int main() { vector<int> input_set; input_set.push_back(-1); input_set.push_back(0); input_set.push_back(1); input_set.push_back(2); input_set.push_back(-1); input_set.push_back(-4); vector<vector<int> > final_set = threeSumIterativeSolution(input_set); // If final_set is empty, then if (final_set.size() == 0) { cout << "No possible combinations found"; return 0; } // print the output for (int i = 0; i < final_set.size(); i++) { if (final_set[i].size() > 0) { cout << " ( "; for (int j = 0; j < final_set[i].size(); j++) cout << final_set[i][j] << " "; cout << ")"; } cout<<endl; } return 0; }
Output:
( -1 0 1 ) ( -1 -1 2 ) ( 0 1 -1 )
As we are using 3 for loops, hence we get time complexity of O (n^3)
Solution 2:
Step 1: Sort the given array.
Step 2: Our problem is a + b + c = 0, we can modify as b + c = -a.
Here “-a” is the large, and “b” “c”.
The solution in C++:
#include<iostream> #include <vector> using namespace std; vector<vector<int> > threeSumWithThreePointers (vector<int>& input_set) { vector<vector<int> > final_result_set; sort(input_set.begin(), input_set.end()); for (int i = 0; i < input_set.size(); i++) { int target = -input_set[i]; // set it to inverse of the first number int front = i + 1; //front pointer int back = input_set.size() - 1; // back pointer if (i > 0 && input_set[i] == input_set[i - 1]) continue; // if there is duplicates for the first pointer // two sum solution with front and back pointers and a target element while (front < back) { int sum = input_set[front] + input_set[back]; if (sum < target) front++; else if (sum > target) back--; else { vector<int> current_combination(3, 0); current_combination[0] = input_set[i]; current_combination[1] = input_set[front]; current_combination[2] = input_set[back]; final_result_set.push_back(current_combination); // Processing duplicates of pointer 2 while (front < back && input_set[front] == current_combination[1]) front++; // Processing duplicates of pointer 3 while (front < back && input_set[back] == current_combination[2]) back--; } } } return final_result_set; } int main() { vector<int> input_set; input_set.push_back(-1); input_set.push_back(0); input_set.push_back(1); input_set.push_back(2); input_set.push_back(-1); input_set.push_back(-4); vector<vector<int> > final_set = threeSumWithThreePointers(input_set); // If final_set is empty, then if (final_set.size() == 0) { cout << "No possible combinations found"; return 0; } // print the output for (int i = 0; i < final_set.size(); i++) { if (final_set[i].size() > 0) { cout << " ( "; for (int j = 0; j < final_set[i].size(); j++) cout << final_set[i][j] << " "; cout << ")"; } cout<<endl; } return 0; }
Output:
( -1 -1 2 ) ( -1 0 1 )
Please write your answers in the comment section of the post below.