3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Notice that the solution set must not contain duplicate triplets.

Approach1 :

We wanto to find a + b + c = 0 which is equivalent to a + b = -c or a + b = target where target = -c. By virtue of this pattern, our 3Sum problem becomes a 2Sum problem.

• We will iterate over the array until length of array - 2. We stopped with two items remaining as we're looking for a triplet set of numbers and at that point, we would have already found any possible combination that would have included these remaining two numbers.

• To avoid duplicates, we insert if i > 0 and nums[i] == nums[i-1] this is because when i = 0, it doesn't need to check if it's a duplicate element since it doesn't even have a previous element to compare with. And nums[i] == nums[i-1] is to prevent checking duplicate again.

• For each iteration of i (first element) we make a standard bi-directionnal 2Sum Sweep of the remaining parts of the array by using two additional pointers.

• if we've found a possible combination, we add to the List, then we keep on looking and again we insert the condition to make sure that we avoid duplicates in the answer without the need for a Set data structure.

bi-directional 2Sum: Since the array is sorted, we are decreasing the sum by moving k downards. If the sum is too small, we need to increase the sum by moving j forwards. k and j represent the bounds of the pointers, so you can't get larger than k, and you can't get smaller than j.

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        
        for(int i = 0; i + 2 < nums.length; i++){
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            int j = i + 1;
            int k = nums.length - 1;
            int target = -nums[i];
            while(j < k){
                if(nums[j] + nums[k] == target){
                    res.add(Arrays.asList(nums[i], nums[j++], nums[k--]));
                    while(j < k && nums[j] == nums[j - 1]) j++;
                    while(j < k && nums[k] == nums[k + 1]) k--;
                }
                else if(nums[j] + nums[k] > target) k--;
                else{
                    j++;
                }
            }
        }
        return res;
    }
}

Time: O(n2) Space: O(n)

Approach2 : Using a HashSet

We're looking for a set of 3 elements which equal 0 cumulatively. This approach is casi-identical to the above with the exception that we will use the properties inherent to a Set to alleviate some of the code. (a Set cannot contain duplicates).

• We iterate over the array until length of array - 2.

• For each iteration of i (first element) we make a standard bi-directionnal 2Sum Sweep of the remaining parts of the array by using two additional pointers.

• if we've found a possible combination (if sum = 0), we add to the Set, then we keep on looking and again.

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Set<List<Integer>> set = new HashSet<>();
        if(nums.length == 0) return new ArrayList<>(set);
        Arrays.sort(nums);
        
        for(int i = 0; i < nums.length - 2; i++){
            int j = i + 1;
            int k = nums.length - 1;
            while(j < k){
                int sum = nums[i] + nums[j] + nums[k];
                if(sum == 0) set.add(Arrays.asList(nums[i], nums[j++], nums[k--]));
                else if(sum < 0) j++;
                else if(sum > 0) k--;
            }
        }
        return new ArrayList<>(set);
    }
}

Approach3: Recursive

Same as Approach2, but recursive.

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        if (nums.length < 3) return new ArrayList<>(); // if nums less than 3 element
        Arrays.sort(nums); // sort array
        Set<List<Integer>> set = new HashSet<>();
        for (int i = 0; i < nums.length - 2; i++) {
            helper(nums, i, i + 1, nums.length - 1, set);
        }

        return new ArrayList<>(set);
    }

    private void helper(int[] nums, int i, int j, int k, Set<List<Integer>> set) {
        if (j >= k) return;
        int sum = nums[i] + nums[j] + nums[k];
        if (sum == 0) {
            set.add(Arrays.asList(nums[i], nums[j++], nums[k--]));
            helper(nums, i, j, k, set);
        } else if (sum > 0) helper(nums, i, j, k - 1, set);
        else helper(nums, i, j + 1, k, set);
    }
}

Time: O(n2) Space: O(n)