Arrays - 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, 0, 1], [-1, -1, 2]] Explanation: There are three triplets which gives sum as 0. nums[0] + nums[1] + nums[2] which is -1 + 0 + 1 = 0 nums[1] + nums[2] + nums[4] which is 0 + 1 + -1 = 0 nums[0] + nums[3] + nums[4] which is -1 + 2 + -1 = 0 Notice that first and second triplets are same, so the unique triplets are [[-1, 0, 1], [-1, -1, 2]].

Example 2

Input: nums = [0, 1, 1] Output: [] Explanation: There are no triplets which sum up to 0.

Example 3

Input: nums = [0,0,0] Output: [[0,0,0]] Explanation: The only possible triplet sums up to 0.

Constraints:

3 <= nums.length <= 3000
-10⁵ <= nums[i] <= 10⁵

Solution 1 - Use the technique from 2 Sum problem and track duplicates using a HashSet
Solution 2 - Sort input array and then apply 2 Sum II solution

Solution 1 - Use the technique from 2 Sum problem and track duplicates using a HashSet

In this approach, we will split the problem into a sub problem of 2 Sum using below steps.

As per the problem statement, we have to find a triplet from the array which sum up to zero, array[i] + array[j] + array[k] =0 .
We can rewrite this as array[j] + array[k] = 0 - array[i].
So, as we loop the array, for each number at i^th index from the array, we will need to find out a pair of numbers at index j and k that adds up to 0 - array[i].

We will use an intermediate data structure HashSet to track of duplicates.

import java.util.*; public class ThreeSum { static List<List<Integer>> threeSum_Using_2Sum(int[] nums) { List<List<Integer>> result = new ArrayList<>(); Set<List<Integer>> duplicates = new HashSet<>(); for(int i=0; i<nums.length; i++) { int num = nums[i]; int twoSum = 0-num; int[] twoSumIndexes = TwoSum.twoSum(nums, twoSum); if(twoSumIndexes != null) { List<Integer> triplet = Arrays.asList(num, nums[twoSumIndexes[0]], nums[twoSumIndexes[1]]); triplet.sort(Comparator.naturalOrder()); // we can assume this is O(1) time as we are sorting just 3 numbers if(!duplicates.contains(triplet)) { duplicates.add(triplet); result.add(triplet); } } } return result; } }

Complexity Analysis:

Above code runs in O(n²) time complexity where n is the size of the input array, as we are looping through the array once, for each element in array we are calling TwoSum algorithm and that runs in O(n) time. Space complexity is O(n).

Solution 2 - Sort input array and then apply 2 Sum II solution

In this approach, we will first sort the input array, so that identifying duplicate triplets is easy and then make the problem into a sub problem of 2 Sum II using the same steps in this solution.
Once the input array is sorted, loop through elements from 0^th index to array.length - 2^th index and for each element, check if i^th element is same as i-1^th element and ignore if they are same.
Reason is that, if a triplet is found at i-1^th index, it will get same triplets at i^th index as well if values are i and i-1 indexes are same.
Next, compute remaining sum needed to make it 0, twoSum = 0-array[i] and initialize two pointer variables low = i +1 and high = array.length-1 to iterate from left and right ends of array respectively until both pointers meet each other.
If you find two numbers such that array[low] + array[high] == twoSum , then we have found one triplet. Now continue checking other possible pairs that adds upto the same twoSum, we also need to avoid duplicates while doing this.

Increment low to next index low = low +1 , and if that is within the bounds of input array, check if nums[i] == nums[i-1], if they are same then keep incrementing low.
We don't need to check right side values, as it automatically gets eliminated, say for example twoSum = 4 and nums[2, 2, 3, 2, 2, 2] and low = 0 and high =5 when the two sum match is found. If we eliminate left side duplicates, we will update low = 2 to point nums[2]= 3, right side values automatically gets eliminated as sum will become either higher or lower than target.

If you find two numbers such that array[low] + array[high] < twoSum , then move low pointer by 1.
If you find two numbers such that array[low] + array[high] > twoSum , then decrement high pointer by 1.

import java.util.*; public class ThreeSum { public List<List<Integer>> threeSum_Using_Sorting_And_2Sum(int[] nums) { Arrays.sort(nums);// n (log n) List<List<Integer>> result = new ArrayList<>(); for (int i=0; i<nums.length-2; i++) { if(i==0 || nums[i] != nums[i-1]) { // since the array is sorted, we can ignore elements i and i-1 if they are same. // reason for that is, if there is a triplet found at i, the same triplet would have been found at i-1 as well int twoSum = 0-nums[i]; int low = i+1; int high = nums.length-1; while(low < high) { if(nums[low] + nums[high] == twoSum) { // two sub problem answer is found, that gives us the triplet (i,low,high) result.add(List.of(nums[i], nums[low], nums[high])); //let's continue, as there could be other triplets with i as one element. //while doing this lets avoid duplicates low++; while(low<high && nums[low] == nums[low-1]) { low++; } } else if (nums[low]+nums[high] <twoSum) { low++; } else { high--; } } } } return result; } }

Complexity Analysis:

Above code runs in O(n²) time complexity where n is the size of the input array. Sorting of input array will take O(n log n) and then we are looping through each element of input array, then for each element in array we are going through input array again. Space complexity is O(n).

Above examples source code can be found at GitHub link for Java code and JUnit tests can be found at GitHub link for Unit tests code

Example 1

Example 2

Example 3

Constraints:

Contents

Complexity Analysis:

Complexity Analysis: