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 != ji != 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;
}
3sum leetcode and interviewbit solution.

Complexity Analysis:

Runtime Complexity: O(n2)

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.

Share your love

Leave a Reply