3Sum Solution Explained for LeetCode InterviewBit GeeksforGeeks

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²)

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? Check Top Interview Questions category.