Today I’m looking at the first problem in the Leetcode July Challenge Week 2 problem set, 3-Sum. 3-Sum is one among a family of problems referred to, at least by me, as k-sum problems, and hopefully you’ll see why mentally grouping such problems is beneficial in finding a solution. The problem presents us with an array of integers and asks that we return a set containing any triplets composed of integers from the array whose sum is equal to zero: $$\forall\; \{a, b, c\} \ni a + b + c = 0$$ For example:

Input: $[-4, -4, -2, 0, 2, 4, 4, 8]$
Output: $[[-4, -4, 8],[-4, 0, 4],[-2, 0, 2]]$

The concept is pretty straightforward, but we have to decide how to process it programmatically. The key observation here is made by categorizing and decomposing the problem. The category, as I pointed out earlier, is that this is a k-sum problem. Ideally we’ve even seen and programmed a couple of these before. The decomposition is that for any k-sum problem, we’re really just working on a k-1-sum problem for each unique element in the input array. Which means that for 3-sum, we just have to find 2-sum for each element. There a few standard approaches to the 2-sum problem, but I prefer using two pointers, left and right, to narrow down solutions within a subarray that starts at element $i+1$, where $i$ is the current 3-sum element. Note: this approach assumes a sorted input array. We can look back at the example to see how this might work:

Input: $[-4, -4, -2, 0, 2, 4, 4, 8]$
$i = -4$
$left = -4$, $right = 8$
$i + left + right == 0$, so we add it to the set and move both pointers towards one another.
$left = -2$, $right = 4$
$i + left + right \lt 0$, so we move the left pointer rightward, which should increase the sum.
$left = 0$, $right = 4$
$i + left + right == 0$, so we add it to the set and move both pointers inward, and so on…

Each iteration of 2-sum has an asymptotic runtime complexity O(n), but it’s also worth mentioning that an amortized average runtime would somewhat improved as each iteration from element $i$ only looks at array elements $i+1…n$ for potential solutions. This give the 3-sum algorithm an overall runtime complexity of O($n^2$). This pattern is repeated for k-sum problems, wherein the asymptotic complexity will be equal to $O(n^{k-1})$. Take a look at the code from my submission, and let me know if you have any questions! I’ll be back tomorrow with another fun July Challenge problem.

vector<vector<int>> threeSum(vector<int>& nums) {
   // if input has less than three elements, no triplets are possible.
   if(nums.size() < 3) return {};

   // sort the input array to meet our 2-sum functions assumption of sorted input.
   sort(nums.begin(), nums.end());

   vector<vector<int>> triplets;
   int prev = INT_MAX;
   for(int i=0;i<nums.size();i++) {
	  // skipping duplicate elements ensures no duplicate triplets in set.
	  if(nums[i] == prev) continue;
	  prev = nums[i];
	  twoSumSorted(nums, i, triplets);
   }
   return triplets;
}
void twoSumSorted(vector<int>& nums, int current, vector<vector<int>>& triplets) {
   int left = current+1, right = nums.size()-1;
   while(left < right) {
	  // skip duplicates on the left and right pointers.
	  if(left > current+1 && nums[left] == nums[left-1]) {
		 left++;
		 continue;
	  }
	  if(right < nums.size()-1 && nums[right] == nums[right+1]) {
		 right--;
		 continue;
	  }
	  // i + left + right
	  int sum = nums[current] + nums[left] + nums[right];
	  if(sum < 0) left++;
	  else if(sum > 0) right--;
	  else triplets.push_back({nums[current], nums[left++], nums[right--]});
   }
}