algorithm - Quadratic algorithm for 4-SUM

Question

The 4-SUM is as follows:

Given an array of N distinct integers find 4 integers a, b, c, d such that a+b+c+d = 0.

I could come up with a cubic algorithm using quadratic algorithm for 3-SUM problem. Can we do better than cubic for 4-SUM?

Answer 1

Yes you can. Go over all pairs of numbers and store their sum(and also store which numbers give that sum). After that for each sum check if its negation is found among the sums you have. Using a hash you can reach quadratic complexity, using std::map, you will reach O(n^2*log(n)).

EDIT: to make sure no number is used more than once it will better to store indices instead of the actual numbers for each sum. Also as a given sum may be formed by more than one pair, you will have to use a hash multimap. Having in mind the numbers are different for a sum X = a1 + a2 the sum -X may be formed at most once using a1 and once using a2 so for a given sum X you will have to iterate over at most 3 pairs giving -X as sum. This is still constant.

Answer 2

There is also a O(N²) algorithm for this problem using O(N²) extra memory.

1. Generate all the pairwise sums in O(N²) and store the pair (a_i, a_j) in a hash table and use the absolute value of their sum as the key of the hash table (a_i and a_j are two distinct numbers of the input array)

2. Iterate over the table and find a key which has both negative and positive sum with four distinctive elements and return is as the answer

There is an alternative if you prefer not using hash table. Since your numbers are integers, you can sort the list of all the sum in a linear time of the elements in the sum list using something like a Radix sort (there are O(N²) elements in the sum list).

Answer 3

Sharing my code for a 4-sum problem, which will give you Quadratic Time complexity. You can run this program with any given sum number. In your case you want the sum to be zero, so passing 0 in function parameters. The idea is we can precompute the sum of a + b and store into a map first if it does not exist in the map, and then we can do c + d and checking if target -(c + d) is in the map.

import java.util.*;

public class FourSumPractice {
    public List<List<Integer>> quadTuple(int[] arr, int len, int sum){
    Map<Integer, Set<List<Integer>>> map = new HashMap<>();
    Set<List<Integer>> res = new HashSet<>();

    for (int i = 0; i < len - 1; i++) {
        for (int j = i + 1; j < len; j++) {
            int requiredSum = sum - (arr[i] + arr[j]);
            if(map.containsKey(requiredSum)){
                for (List<Integer> l : map.get(requiredSum)) {
                    int x = l.get(0);
                    int y = l.get(1);

                    if((x != i && x != j) && (y != i && y != j)){
                        List<Integer> quard = Arrays.asList(arr[i], arr[j], arr[x], arr[y]);
                        Collections.sort(quard);
                        res.add(quard);
                    }
                }
            }
            map.putIfAbsent(arr[i] + arr[j], new HashSet<>());
            map.get(arr[i] + arr[j]).add(Arrays.asList(i,j));
        }
    }
    return new ArrayList<>(res);
}

public static void main(String[] args)
{
    int[] A = { -10, 30, -15, -5, -5, -25, 0, 10, 51 };
    int sum = 0;
    FourSumPractice obj = new FourSumPractice();
    List<List<Integer>> l = obj.quadTuple(A, A.length, sum);
    for(List<Integer> sub:l){
        for(int i : sub){
            System.out.print(" "+ i);
        }
        System.out.println(" ");
       }
    }
}