[LeetCode] 4Sum II

Problem: Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -2^28 to 2^28 - 1 and the result is guaranteed to be at most 2^31 - 1.

Example:

Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

Output:
2

Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

Approach: Let's have a look at the basic brute-force approach first to solve this question. Basically we will try every tuple (i, j, k, l) to see if A[i] + B[j] + C[k] + D[l] is 0 or not. If yes, add 1 to our result. Here is the approach looks like:

• result = 0
• FOR i = 0 to n
• FOR j = 0 to n
• FOR k = 0 to n
• FOR l = 0 to n
• IF A[i] + B[i] + C[i] + D[j] eq 0
• result = result + 1
• RETURN result

This approach will solve the problem but it is very expensive and it will take O(n^4) time. Let's see how we can reduce the run time. 

If we hash every element of A into say AMap where key is element of A and value is its number of occurrences in A then we just need to check for every tuple (j, k, l) to see if -(B[j] + C[k] + D[l]) exist in the AMap or not. If yes then we add AMap[-(B[j] + C[k] + D[l])] to the result. This approach will look like:

• AMap = {}
• FOR i = 0 to n
• AMap[A[i]] = AMap[A[i]] + 1
• result = 0
• FOR j = 0 to n
• FOR k = 0 to n
• FOR l = 0 to n
• IF AMap contains  -(B[i] + C[i] + D[j])
• result = result + AMap[-(B[i] + C[i] + D[j])]
• RETURN result

So now if you see we have reduced one loop from the nested loops of our first approach. Hence this approach will solve this problem in O(n^3) which is considerable improvement from from our first approach. Let's see how can we do even better.

If we hash every sum of tuple (i, j) where sum is A[i] + B[j] into say ABMap where key is (A[i] + B[j]) and value is number of times this sum came then we just need to check for every tuple (k, l) to see if -(C[k] + C[l]) exist in ABMap or not and if yes then we add ABMap[-(A[i] + B[j])] to the result. Here is how this approach looks like:

• ABMap = {}
• FOR i = 0 to n
• FOR j = 0 to n
• ABMap[A[i] + B[j]] = ABMap[A[i] + B[j]] + 1
• result = 0
• FOR k = 0 to n
• FOR l = 0 to n
• IF ABMap contains  -(C[i] + D[j])
• result = result + ABMap[-(C[i] + D[j])]
• RETURN result

This approach will solve the problem in O(n^2) time and is the most optimal approach I can think of.

Implementation in C#:

    public int FourSumCount(int[] A, int[] B, int[] C, int[] D) 

    {        

        Dictionary<int, int> abSums = new Dictionary<int, int>();

        for (int i = 0; i < A.Length; ++i)

        {

            for (int j = 0; j < B.Length; ++j)

            {

                int sum = A[i] + B[j];

                if (!abSums.ContainsKey(sum))

                {

                    abSums.Add(sum, 0);

                }

                ++abSums[sum];

            }

        }        

        int result = 0;        

        for (int i = 0; i < C.Length; ++i)

        {

            for (int j = 0; j < D.Length; ++j)

            {

                int sum = C[i] + D[j];

                if (abSums.ContainsKey(-sum))

                {

                    result += abSums[-sum];

                }

            }

        }        

        return result;

    }

Complexity: O(n^2)