3Sum is one of the most frequently asked questions in software coding interviews. It tests your skills on the 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 correspond** **to assigning two variables two different points in the array and keeping** **to move them toward each other and once you found the solution then add it to the solution array and keep moving unless both pointers come to the same point.**

### Solution in C++

//C++ Code Example 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**.