# 3Sum Solution for LeetCode InterviewBit Explained

3Sum is one of the most frequent asked question in software coding interviews. It tests your skills on two pointer algorithm.

And if you are aware of two pointer algorithm then it must be easy to solve. In this post I will be discussing the two pointer method and when you can use it to achieve the desired solution for the coding interview questions.

## Question: 3SUM

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.

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 = 
Output: []```

## Algorithm and Solution to 3Sum in LeetCode and InterviewBit

So, the major algorithm used here is two pointers. Two pointers basically corresponds to assigning two variables two different points in array and keep moving them toward each other and once you found the solution then add it to the solution array and keep moving unless both pointer comes to same point.

### Solution in C++

```vector<vector<int>> threeSum(vector<int>& nums) {
std::vector<vector<int>> finalRes;
if (nums.empty()) {
return finalRes;
}

std::size_t n_size = nums.size();
std::sort(nums.begin(), nums.end());
for (int i = 0; i < n_size; ++i) {
// all numbers from now on will be greater than 0, no point in continuing
if (nums[i] > 0) break;

// we have seen this number & combo before; skip
if (i > 0 and nums[i] == nums[i-1]) continue;

int leftPointer = i+1, rightPointer = n_size - 1;
while (leftPointer < rightPointer) {
int sum = nums[i] + nums[leftPointer] + nums[rightPointer];
if (sum < 0) {
++leftPointer;
} else if (sum > 0) {
--rightPointer;
} else {
finalRes.push_back({nums[i], nums[leftPointer], nums[rightPointer]});
int last_left = nums[leftPointer], last_right = nums[rightPointer];
// we have seen this number & combo before; skip
while (leftPointer < rightPointer && nums[leftPointer] == last_left) ++leftPointer;
while (leftPointer < rightPointer && nums[rightPointer] == last_right) --rightPointer;
}
}

}
return finalRes;
}```

### Complexity Analysis:

Runtime Complexity: O(n2)

Space Complexity: O(n)