3Sum

Given an array nums of n integers, are there elements abc 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.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Example 2:

Input: nums = []
Output: []

Example 3:

Input: nums = [0]
Output: []

Constraints:

  • 0 <= nums.length <= 3000
  • -105 <= nums[i] <= 105

This problem is also known as the 3SUM Problem. The 3SUM problem asks if a given set of real numbers contains three elements that sum to zero. The problem cannot be solved better than an O(n2) solution. There are brute force solutions available, that can find all the triplets from an array in O(n3) time. But here we are going to discuss an O(n2) solution using a HashSet. Consider the following example:

Note: The solution set must not contain duplicate triplets.

The method signature of the given solution is as follows:

public static <List> getTriplets(int[] arr)

So, the method getTriplets is taking the input array as an argument and returns a List of List, where each of the inner lists represents a subarray of 3 elements that sum to Zero (Called Triplet here). Following is the pseudo-code for the solution:

We need to find all the subarray from a given array where : (a+b+c) = 0.

a + b + c = 0
=> c = -a-b
=> c = - (a+b)

Algorithm:

outer for loop ( i = 0 to i < arr.length)
    int a = arr[i];
    inner for loop  ( j= (i+1) to j < arr.length)
        Set<Integer> set = new HashSet<>();
        int b = arr[j];
        int c = -(a+b);
        if(c is present in the HashSet)
            triplet is a,b,c
        else
            add b to HashSet

Consider the Following Java implementation:

import java.util.*;

public class ThreeNumberSumToZero {

    public static void main(String[] args) {
        int arr[] = {3, -1, -7, -4, -5, 9, 10,-2};
        List<List<Integer>> list = getTriplets(arr);
        System.out.println(list);
    }

    public static List<List<Integer>> getTriplets(int[] nums) {

        if (nums == null || nums.length < 3) {
            return new ArrayList<>();
        }

        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int a = nums[i];
            Set<Integer> search = new HashSet<>();
            for (int j = (i + 1); j < nums.length; j++) {
                int b = nums[j];
                int c = -(a + b);
                if (search.contains(c)) {
                    List<Integer> triplet = Arrays.asList(a, b, c);
                    Collections.sort(triplet);
                    if(!result.contains(triplet)){
                        result.add(triplet);
                    }
                } else {
                    search.add(b);
                }
            }
        }
        return result;
    }
}

Approach 2: Sorting

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        
        List<List<Integer>> result = new ArrayList<>();
        if(nums == null || nums.length == 0){
            return result;
        }
        int n = nums.length;
        Arrays.sort(nums);
        Set<String> seen = new HashSet<>();
        for(int i = 0 ; i < n ; i++){
            int left = nums[i];
            int m = i+1;
            int r = n-1;
            while(m < r){
                int mid = nums[m];
                int right = nums[r];
                int cur_sum = left + mid + right;
                if(cur_sum == 0){
                    String key = left + "_" + mid + "_" + right;
                    if(!seen.contains(key)){
                        List<Integer> triplet = new ArrayList<>();
                        triplet.add(left);
                        triplet.add(mid);
                        triplet.add(right);
                        result.add(triplet);
                        seen.add(key);
                    }
                    m++;
                    r--;
                }else if(cur_sum > 0){
                    r--;
                }else{
                    m++;
                }
            }
        }
        return result;
    }
}

Categories: Array

Tagged as: , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s