3 Sum

Share

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:

Contents

Solution 1 - Use the technique from 2 Sum problem and track duplicates using a HashSet
  1. 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].
  2. So, as we loop the array, for each number at ith 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].
Java
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(n2) 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
  1. 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.
  2. 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.
Java
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(n2) 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