# Solution by two pointer

• #### Approach #1 Brute Force [Time Limit Exceeded]

Intuition

Find all unique triplets of the given array which gives the sum of zero.
Here unique means there are no two triplets \$a_{1}, b_{1}, c_{1}\$ and \$a_{2}, b_{2}, c_{2}\$ where:-
\$a_{1} == a_{2} &amp;&amp; b_{1} == b_{2} &amp;&amp; c_{1} == c_{2}\$ satisfied.

Algorithm

First ignore the unique condition. To find all thriplets, what we need to do?

• Use three nested loop for \$a, b & c\$, and generate all possible combination.

C++

``````class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<int> t(3);
vector< vector<int> > triplets;
int n = nums.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
if (nums[i] + nums[j] + nums[k] == c) {
t[0] = nums[i];
t[1] = nums[j];
t[2] = nums[k];
triplets.push_back(t);
}
}
}
}
return ans;
}
};
``````

But here out solution is not unique. For same \$a\$ and \$b\$ only one real number is possible for \$c\$, that is \$c = - (a + b)\$.
If more than one \$c\$ exists in the array, we take one to be unique of our solution.
Now, our goal is to compute \$a\$ and \$b\$ uniquely. For all possible unique \$a\$, if we select all unique \$b\$, here \$(b >= a)\$ than all \$a, b\$ pair must be unique.

C++

``````class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<int> t(3);
vector< vector<int> > triplets;
sort(nums.begin(), nums.end());
int n = nums.size();
cout << n << endl;
for (int i = 0; i < n; i++) {
// a should be unique, so ignore
// if we use same value before
if (i > 0 && nums[i] == nums[i-1]) {
continue;
}
for (int j = i + 1; j < n; j++) {
// b also unique for every a, so ignore
// if we use same value before for this ai
if (j > i + 1 > 0 && nums[j] == nums[j-1]) {
continue;
}
for (int k = j + 1; k < n; k++) {
if (nums[i] + nums[j] + nums[k] == 0) {
t[0] = nums[i];
t[1] = nums[j];
t[2] = nums[k];
triplets.push_back(t);
break;      // To be soluton unique break after find one c
}
}
}
}
return triplets;
}
};
``````

Complexity Analysis

• Time complexity : \$O(n^3)\$.

Fist we sort the given array. Complexity for this \$n log(n)\$.
After that use three nested loop to select \$a, b\$ and \$c\$.
In worst case these three loop run \$n, n - 1\$ and \$n - 2\$ times.
So total time complexity is:
\$\$O(nlog(n)) + n * (n - 1) * (n - 2)\$\$
\$\$ = O(nlog(n)) + n^3 - 3n^2 + 2n\$\$
\$\$ = O(nlog(n)) + O(n^3)\$\$
\$\$ = O(n^3)\$\$

#### Approach #2 Use Binary Search [Accepted]

Algorithm

Here \$a + b + c = 0\$, hence \$c = -(a + b)\$.
So in third loop we need to know if \$-(a + b)\$ is exist or not.
We already sort the array, so we can use binary search.

C++

``````class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<int> t(3);
vector< vector<int> > triplets;
sort(nums.begin(), nums.end());
int n = nums.size();
cout << n << endl;
for (int i = 0; i < n; i++) {
if (i > 0 && nums[i] == nums[i-1]) {
continue;
}
for (int j = i + 1; j < n; j++) {
if (j > i + 1 > 0 && nums[j] == nums[j-1]) {
continue;
}
int c = -(nums[i] + nums[j]);
if (binary_search(nums.begin() + j + 1, nums.end(), c)) {
t[0] = nums[i];
t[1] = nums[j];
t[2] = c;
triplets.push_back(t);
}
}
}
return triplets;
}
};
``````

Complexity Analysis

• Time complexity : We use binary search instead of third loop. So time complexity is: \$O(n^2log(n))\$

#### Approach #3 Us two pointer [Accepted]

Algorithm

Here \$a + b + c = 0\$, hence \$b + c = -a\$.
So for all \$a\$ we need to find number of unique pair which sum gives \$-a\$.
We can do it linear time using two pointer.

C++

``````class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<int> t(3);
vector< vector<int> > triplets;
sort(nums.begin(), nums.end());
int n = nums.size();
for (int i = 0; i < n; i++) {
if (i > 0 && nums[i] == nums[i-1]) {
continue;
}
int b = i + 1, c = n - 1, a = -nums[i];
while (b < c) {
while (b < c && nums[b] + nums[c] > a) {
c--;
}
while (b < c && nums[b] + nums[c] < a) {
b++;
}
if (b < c && nums[b] + nums[c] == a) {
t[0] = nums[i];
t[1] = nums[b];
t[2] = nums[c];
triplets.push_back(t);
b++;
}
while (b < c && nums[b] == nums[b - 1]) {
b++;
}
}
}
return triplets;
}
};
``````

Complexity Analysis

• Time complexity : We use We iterate full array for first number. For rest two number we iterate rest of the array. So time complexity is: \$O(n^2)\$

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.