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 = [0]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(n^{2})

Space Complexity: O(n)

If you liked the answer then please follow us on **Facebook **and **Twitter**. Let us know the questions and answer you want to cover in this blog.

Wanna read more interview related questions ? **Che****ck Top Interview Questions category**.