10. 3Sum

#leetcode/15

Problem 🔗

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:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Solution

Solution in C++ using hash map

Using a hashmap, the idea is similar to 3. Two Sum.

1. Sort the input array
2. Store the index of the last occurrence of each number in a hashmap
3. Iterate through the array with a variable i, starting from index 0
4. Nested loop with a variable j, with j starting at i+1, and a variabile required = -(nums[i] + nums[j])
5. In the for loop, check if hashMap.contains(required), and if true, add {nums[i], nums[j], required} to the output array
6. To avoid duplicates, we skip equal consecutive numbers

Graphic explanation:

Here's the implementation.

vector<vector<int>> threeSum(vector<int>& nums) {
	sort(nums.begin(), nums.end());
	
	if(nums.size() < 3 || nums[0] > 0) return {};

	vector<vector<int>> ans;
	unordered_map<int, int> hashMap;
	int n = nums.size();

	//store the index of the last occurrence of each number in a hashmap
	for(int i = 0; i < n; i++)
		hashMap[nums[i]] = i;
	
	for(int i = 0; i < n && nums[i] <= 0; i++) {
		//to avoid duplicates, we skip equal consecutive numbers
		int next = hashMap[nums[i]];
		for(int j = i + 1; j < n; j++) {
			int required = -(nums[i] + nums[j]);
			//to avoid duplicates, we skip equal consecutive numbers
			int next = hashMap[nums[j]];
			//if required is in the array and its index > j
			if(hashMap.contains(required) && hashMap[required] > j)
				ans.push_back({nums[i], nums[j], required});
			j = next;
		}
		i  = next;
	}
	return ans;
}

• Time complexity: $O(n^2)$ (where n is the size of the vector)
• Space complexity: $O(n)$ (we are storing all the input)

Solution in C++ using two pointers

Since the array is sorted, we can use a two pointers approach (three actually). One will be at the beginning of the array, the other at the end. In details:

1. Iterate through the array with a variable i, starting from index 0
2. If i is +ve, break there because we can't make it zero by searching after it
3. If number is getting repeated, ignore the lower loop and continue. This is for unique triplets. We want the last instance of the fixed number, if it is repeated.
4. Make two pointers start and end
5. Search between two pointers, just similar to binary search. We call sum = nums[i] + nums[start] + nums[end]
6. If sum is -ve, means, we need more +ve numbers to make it 0, increment start
7. If sum is +ve, means, we need more -ve numbers to make it 0, decrement end
8. If sum is 0, that means we have found the required triplet, push it in answer vector
9. Now again, to avoid duplicate triplets, we have to navigate to last occurences of num[start] and num[end] respectively. Update the start and end with last occurences of low and high

Graphic explanation:

Here's the implementation.

vector<vector<int>> threeSum(vector<int>& nums) {
	sort(nums.begin(), nums.end());
	
	if(nums.size() < 3 || nums[0] > 0) return {};

	vector<vector<int>> ans;
	
	int n = nums.size();
   
	for(int i = 0 ; i < n - 1 && nums[i] <= 0; i++) {
		int start = i + 1, end = n - 1;
		while(start < end) {
			if(nums[i] + nums[start] + nums[end] > 0)
				end--;
			else if(nums[i] + nums[start] + nums[end] < 0)
				start++;
			else {
				ans.push_back({nums[i], nums[start], nums[end]});
				int currStart = start;
				int currEnd = end;
				//to avoid duplicates, we skip equal consecutive numbers
				while(start < end && nums[start] == nums[currStart]) start++;
				while(start < end && nums[end] == nums[currEnd]) end--;
			}
		}
		//to avoid duplicates, we skip equal consecutive numbers
		while(i + 1 < n && nums[i] == nums[i + 1]) i++;
	}
	return ans;
}

• Time complexity: $O(n^2)$ (where n is the size of the vector)
• Space complexity: $O(1)$