3Sum

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

Note:
Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
The solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4},

A solution set is:
(-1, 0, 1)
(-1, -1, 2)

This questions is very much like the 2 sum question. The only difficult part is the duplicate removal. Assume we have an sorted array.

First lets look at how to remove duplicate when you do the 2 sum. 2 pointers move from the head and tail to the middle, we simply ignore all the duplicate until two pointers are pointing to the same element. Why? it is a sorted array so if two numbers are duplicate and at the same time adding to the target, they must be in the middle. Other duplicate can only appear once. Then we check if there are duplicate element and if they are adding to target, if so, add them to the result.

The 3 sum duplicate removal is relatively simple. Pick one element and check the right of the array to find 2 sum. You don’t need to go backward to the left because trplet with the left element is already checked. To remove duplicate, you need to skip all the duplicate element, once it is used. As an example, if the target is 0 and array is -2, -2, -2, 0, 2, 2, 4. When you check the first -2, you get the two sum of the left of the array with target 2. you get {-2, 4} and {0,2}, then you merge with the -2 and get {-2, -2, 4} and {-2, 0, 2}. Then you don’t need to check the second and third -2 because they already covered by the 2 sum (2 sum handles duplicate remember?). You can simply jump to 0 and check.

What is the run time of the algorithm?

Sorting takes nlogn time, then for every element i, find the rest 2sum takes n-i time, there are total of n element so the total run time for scanning is n + (n-1) + (n-2) … = n^2 time. The total run time is then O(n^2).

public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        Arrays.sort(num);
        return Sub3Sum(num);
    }
    
    public ArrayList<ArrayList<Integer>> Sub3Sum(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (num.length < 3)
            return res;
        if (num.length == 3) {// 3 elements
            if (num[0] + num[1] + num[2] == 0 ) {
                ArrayList<Integer> temp = new ArrayList<Integer> ();
                temp.add(num[0]);
                temp.add(num[1]);
                temp.add(num[2]);
                res.add(temp);
            }
            return res;
        }
        //if more than 3 elements, pick one and search rest for 2
        for (int i = 0; i < num.length - 2; i++) {
            int curr = num[i];
            ArrayList<ArrayList<Integer>> next = TwoSum(num, i+1, 0-curr);
            if (!next.isEmpty()) {
                for (ArrayList<Integer> pair: next) {
                    ArrayList<Integer> temp = new ArrayList<Integer>();
                    for (int n : pair) {
                        temp.add(n);
                    }
                    temp.add(0,curr);
                    res.add(temp);
                }
            }
            while(num[i] == num[i+1] && i < num.length-2)// skip same element
                i++;
        }
        return res;
    }
    
    public ArrayList<ArrayList<Integer>> TwoSum(int [] num, int start, int target) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        int l = start;
        int r = num.length-1;
        //two pointer scan from head and tail to mid
        while(num[l] < num[r]) {// to avoid duplicate, skip all the dup element, until two pointer reached the same element
            if (num[l] + num[r] > target)
                do{
                    r--;
                    if (num[l] == num[r])
                        break;
                }while(num[r] == num[r+1]);
            else if (num[l] + num[r] < target)
                do{
                    l++;
                    if (num[l] == num[r])
                        break;
                }while(num[l] == num[l-1]);
            else { // target found
                ArrayList<Integer> temp = new ArrayList<Integer>();
                temp.add(num[l]);
                temp.add(num[r]);
                res.add(temp);
                do{
                    r--;
                    if (num[l] == num[r])
                        break;
                }while(num[r] == num[r+1]);
                do{
                    l++;
                    if (num[l] == num[r])
                        break;
                }while(num[l] == num[l-1]);
            }
        }
        //if the mid has two element and these two elements can fit target, record
        if (r != l && num[l] == num[r] && num[l]*2 == target)
        {
            ArrayList<Integer> temp = new ArrayList<Integer>();
            temp.add(num[l]);
            temp.add(num[r]);
            res.add(temp);
        }
        return res;
    }
}

Using hashSet to remove duplicates. Hashmap map counts the number of appearence of elements. everytime you pick one element from the hashmap, reduce the count by 1 and if you have more than 1 count element left after picking num[i] and num[j]. Then you can pick this element as the third element.

public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();// map integer and count the number
        for (int i = 0; i < num.length; i++) {
            if (map.containsKey(num[i])) {
                map.put(num[i], map.get(num[i]) + 1);
            }
            else {
                map.put(num[i], 1);
            }
        }
        HashSet<triplet> resSet = new HashSet<triplet>();
        for (int i = 0; i < num.length - 2; i++) {// i as the first element
            for (int j = i+1; j < num.length; j++) {
                if (map.containsKey(0 - (num[i] + num[j]))) {
                    int count = map.get(0 - (num[i] + num[j]));
                    int target = 0 - num[i] - num[j]; // the third number
                    if (target == num[i])
                        count--;
                    if (target == num[j])
                        count--;
                    if (count >= 1) {
                        triplet t = new triplet(num[i], num[j], (0 - (num[i] + num[j])));
                        resSet.add(t);
                    }
                }
            }
        }
        
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        for (triplet t : resSet) {
            res.add(t.toArrayList());
        }
        return res;
    }
    
    public class triplet {
        int [] tmp = new int [3];
        public triplet(int x, int y, int z) {
            tmp[0] = x;
            tmp[1] = y;
            tmp[2] = z;
            Arrays.sort(tmp);
        }
        @Override 
        public boolean equals (Object obj) {
            if (obj instanceof triplet) {
                triplet t = (triplet) obj;
                return t.tmp[0] == this.tmp[0] && t.tmp[1] == this.tmp[1] && t.tmp[2] == this.tmp[2];
            }
            else
                return false;
        }
        @Override 
        public int hashCode() {
            int res = 0;
            for (int i = 0; i < tmp.length; i++) {
                res += 31*res + tmp[i];
            }
            return res;
        }
        
        public ArrayList<Integer> toArrayList() {
            ArrayList<Integer> res = new ArrayList<Integer>();
            for (int i : tmp)
                res.add(i);
            return res;
        }
    }
}

Use sorting, and without duplication reduction using hashset.
Because all the elements are already sorted, so the idea is if you have tried one element at position 0, don’t try the same element in position 0 again. Same for position 1 and 2. Use last1 and last2 element to keep track of the the last element that was positioned in position 0 and 1. for position 2, simply look for the last triplet put into the result list

public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        Arrays.sort(num);
        int last1 = Integer.MIN_VALUE;
        int last2 = Integer.MIN_VALUE;
        for (int i = 0; i < num.length - 2; i++) {
            //skip all the same element in position 0
            if (num[i] == last1)
                continue;
            int j = i+1; 
            int k = num.length-1;
            while(j < k) {
                //skip all the same element in postion 1
                if (num[j] == last2) {
                    j++;
                    continue;
                }
                if (num[j] + num[k] + num[i] == 0) {
                    ArrayList<Integer> triplet = new ArrayList<Integer>();
                    if (res.isEmpty() || !(res.get(res.size()-1).get(0) == num[i] && (res.get(res.size()-1).get(1) == num[j] && (res.get(res.size()-1).get(2) == num[k])))) {
                        triplet.add(num[i]);
                        triplet.add(num[j]);
                        triplet.add(num[k]);
                        res.add(triplet);
                        last1 = num[i];
                        last2 = num[j];
                        triplet = new ArrayList<Integer>();
                    }
                    k--;
                    j++;
                }
                else if (num[j] + num[k] + num[i] > 0)
                    k--;
                else
                    j++;
            }
            last2 = Integer.MIN_VALUE; // invalidate last2 if last1 has changed.
        }
        return res;
    }
}

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s