Scribble 1: Triplet Sum

Here’s the problem statement:
Given an array of unique integers, find all triplets of distinct integers (in any order) that add up to a given target sum.

For example:
The array: 4, 19, 8, 6, -1, 15, 10
Target sum: 13
Output: [[4, -1, 10,], [-1, 6, 8]]

Let’s dive into the solution: We can extend the approaches used to solve the Pair Sum problem to find the required triplets.
Let’s see how to extend Pair Sum problem’s Approach 2:

The reason for looking only at elements that lie after the current element is that if there was a triplet possible which included any of the elements that lie behind the current element then it would have been discovered when we were looping over that element earlier in the outer loop.

Time Complexity: 1. Sorting at avg: O(n.logn) 2. Looping over integers using doubly nested loops: O(n²). Therefore overall avg. time complexity: O(n²)
Space Complexity (other than the space needed for sorting (if any)): O(n) including the space needed to store the final ans list.

Here’s the solution for the algorithm coded in Java:

public static List<int[]> tripletSum(int[] array, int target) {
	int n = array.length;
	List<int[]> ans = new ArrayList<>();
	Arrays.sort(array);
	for(int i=0;i<=n-3;i++) {
		int curr = i;
		int left = i+1;
		int right = n-1;
		while(left<right){ /* note that the code in this while loop follows the Approach 2 for the Pair Sum problem */
			if((array[curr]+array[left]+array[right]) == target) {		
				ans.add(new int[]{array[curr],array[left],array[right]});
				/* we now increment i and decrement j to discover any other triplets possible that include array[curr] */
				left++;
		 		right--;
			}
			else if((array[curr]+array[left]+array[right]) < targetSum) {
				left++;
			}
			else {
				right--;
			}
		}
	}
	return ans;
}

Also, note that we could of course extend Approach 1 and Approach 3 for the Pair Sum problem to arrive at the solution for Triplet Sum. But realise that using Approach 1, we’ll have time complexity: O(n^3) and space complexity: O(1),
while using Approach 3, we’ll have time complexity: O(n^2) and space complexity: O(N).

Please do let me know if you find this article useful. Also, it’ll be great if you’d provide some feedback. To reach out, please leave a comment in the Contact section. Thanks! Happy Coding! 🙂