4Sum

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

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

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

One way of solving this problem is using the same method solving 3 Sum. We simply need another loop to fix first 2 element, then use two pointers to scan rest of the array from 2 ends to the middle. We can use a hashset to do duplication removal or use the same method as in the 3 Sum during searching. This will take O(n^3) time and O(1) space.

The below is another way, which takes O(n^2) time, but uses O(n) space. The idea is to scan pair by pair, put all the pairs in a hashMap where key is the sum of the pair, and value is a list containing the indexes of each pair. When you have a new pair comes in, first search if there are any pair that sums to “target – num[pair.x] – num[pair.y]”. If so, check the list under the sum and see if there are any duplicate pair (if x or y has one same, which means you are using the same index twice, then you skip that pair). After you found a pair that matches, put both pair into the final result. Duplication removal also requires another hashSet which checks wether the four numbers are already in the set.

The idea is simple, in terms of implementation we need to overload the hashcode and the equals method to porperly use self defined class as key in hashSet/Map.

public class Solution {
    public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (num.length<4)
            return res;
        HashMap<Integer, ArrayList<Pair>> set = new HashMap<Integer, ArrayList<Pair>>(); // make sure not using same element twice
        HashSet<result> resultSet = new HashSet<result>(); // make sure no dup result
        for (int i = 0; i < num.length-1; i++) {
            for (int j = i+1; j < num.length; j++) {
                if (set.containsKey(target - num[i] - num[j])) {
                    ArrayList<Pair> list = set.get(target-num[i]-num[j]);
                    for (Pair p : list) {
                        if (!p.equals(new Pair(i, j))) {
                            result r = new result(num[i], num[j], num[p.x], num[p.y]);
                            if (!resultSet.contains(r)) {
                                resultSet.add(r);
                                res.add(r.getResult());
                            }
                        }
                    }
                }
                if (set.containsKey(num[i] + num[j])) {
                    set.get(num[i] + num[j]).add(new Pair(i, j));
                } 
                else {
                    ArrayList<Pair> temp = new ArrayList<Pair>();
                    temp.add(new Pair(i, j));
                    set.put(num[i] + num[j], temp);
                }
            }
        }
        return res;
        
    }
    
    public class Pair { // pair to store index.
        int x, y;
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        } 
        
        @Override 
        public boolean equals(Object obj) {
            if (!(obj instanceof Pair)) {
                return false;
            }
            Pair p = (Pair)obj;
            if (p.x == this.x || p.x == this.y || p.y == this.x || p.y == this.y) // if there is one same index, can not use the pair
                return true;
            return false;
        }
    }
    
    public class result { // use to remove dup and sort
        int [] temp = new int[4]; 
        public result(int j, int k, int m, int n) {
            temp[0] = j;
            temp[1] = k;
            temp[2] = m;
            temp[3] = n;
            Arrays.sort(temp);
        }
        
        public ArrayList<Integer> getResult() {
            ArrayList<Integer> t = new ArrayList<Integer>();
            for (int i = 0; i<4; i++) {
            	t.add(temp[i]);
            }
            return t;
        }
        
        
        @Override
        public boolean equals(Object obj) {
            if (!(obj instanceof result)) {
                return false;
            }
            result r = (result) obj;
            for (int i = 0; i < 4; i++) {
                if (temp[i] != r.temp[i])
                    return false;
            }
            return true;
        }
        
        @Override
        public int hashCode() {
            int res = temp[0];
            for (int i = 1; i < 4; i++) {
                res = res*31 + temp[i];
            }
            return res;
        }
    }
}

Use sorting, the idea is that if you tried one element at one place, dont try the same in the same place, just skip all the same element when trying to find next.

To get rid of duplicate, record the last used elements, because there will be no e and s pair that have the same s or e but with same sum, so just record them and skip if any s or e is duplicate for the next iteration

public class Solution {
    public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (num.length < 4)
            return res;
        Arrays.sort(num);
        int last1 = Integer.MIN_VALUE;
        for (int i = 0; i < num.length - 3; i++) {
            if (num[i] == last1)
                continue;
            int last2 = Integer.MIN_VALUE;
            for (int j = i+1; j < num.length - 2; j++) {
                if (num[j] == last2)
                    continue;
                int s = j+1;
                int e = num.length - 1;
                int last3 = Integer.MIN_VALUE;
                int last4 = Integer.MIN_VALUE;
                while(s < e) {
                    if (num[s] == last3) {
                        s++;
                        continue;
                    }
                    if (num[e] == last4) {
                        e--;
                        continue;
                    }
                    if (num[i] + num[j] + num[s] + num[e] == target) {
                        ArrayList<Integer> tmp = new ArrayList<Integer>();
                        tmp.add(num[i]);
                        tmp.add(num[j]);
                        tmp.add(num[s]);
                        tmp.add(num[e]);
                        //no duplicate
                        last1 = num[i];
                        last2 = num[j];
                        last3 = num[s];
                        last4 = num[e];
                        s++;
                        e--;
                        res.add(tmp);
                    }
                    else if (num[i] + num[j] + num[s] + num[e] < target) {
                        s++;
                    }
                    else {
                        e--;
                    }
                }
            }
        }
        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