How to improve the performance of Leetcode 4sum-ii challenge

Question

It is a leet code contest question which I am trying to attempt after contest is over but my code always exceeds time limit. Question is

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²⁸ to 2²⁸ - 1 and the result is guaranteed to be at most 2³¹ - 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

My code is

public static int FourSumCount(int[] A, int[] B, int[] C, int[] D)
    {
        int count = 0;
        List<int> map1 = new List<int>();
        List<int> map2 = new List<int>();

        for (int i = 0; i < A.Length; i++)
            for (int y = 0; y < B.Length; y++)
            {
                map1.Add(A[i] + B[y]);
                map2.Add(C[i] + D[y]);
            }
        for (int i = 0; i < map2.Count(); i++)
        {
            for (int j = 0; j < map2.Count(); j++)
                //if (map1.Contains(map2[i]*-1))
                //{
                //    var newList = map1.FindAll(s => s.Equals(map2[i] * -1));
                //    count = count + newList.Count();
                //}
                if (map1[i] + map2[j] == 0)
                {
                    count++;
                }
        }


        return count;
    }

is there any better way? Thanks in anticipation.

Answer 1

I suggest kind of meet in the middle algorithm:

 A[i] + B[j] + C[k] + D[l] = 0

actually means to find out A[i] + B[j] and C[k] + D[l] such that

 (A[i] + B[j]) == (-C[k] - D[l])

We can put all possible A[i] + B[j] sums into a dictionary and then, in the loop over -C[k] - D[l], try to look up in this dictionary. You can implement it like this:

  private static int FourSumCount(int[] A, int[] B, int[] C, int[] D) {
    // left part: all A[i] + B[j] combinations
    Dictionary<int, int> left = new Dictionary<int, int>();

    // loop over A[i] + B[j] combinations
    foreach (var a in A)
      foreach (var b in B) {
        int k = a + b;
        int v; 

        if (left.TryGetValue(k, out v))  
          left[k] = v + 1; // we have such a combination (v of them)
        else 
          left.Add(k, 1);  // we don't have such a combination
      }

    int result = 0;

    // loop over -C[k] - D[l] combinations
    foreach (var c in C)
      foreach (var d in D) {
        int v;

        if (left.TryGetValue(-c - d, out v)) 
          result += v;
      } 

    return result;
  }

As you can see, we have O(|A| * |B| + |C| * |D|) complexity; in case A, B, C and D arrays have the approximately equal sizes N the complexity is O(N**2).

Answer 2

Your first step is okay. But use Dictionary instead of List which will ensure constant time lookup and reduce the complexity of second part.

This was my C++ O(n^2) solution:

int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
    int n = A.size();
    int result = 0;
    unordered_map<int,int> sumMap1;
    unordered_map<int,int> sumMap2;

    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            int sum1 = A[i] + B[j];
            int sum2 = C[i] + D[j];
            sumMap1[sum1]++;
            sumMap2[sum2]++;
        }
    }
    for(auto num1 : sumMap1) {
        int number = num1.first;
        if(sumMap2.find(-1 * number) != sumMap2.end()) {
            result += num1.second * sumMap2[-1 * number];
        }
    }
    return result;
}

The core observation is - if W + X + Y + Z = 0 then W + X = -(Y + Z).

Here I used two hash-tables for each of possible sums in both (A, B) and (C, D) find number of occurrences of this sum.

Then, for each sum(A, B) we can find if sum(C, D) contains complimentary sum which will ensure sum(A, B) + sum(C, D) = 0. Add (the number of occurrences of sum(a, b)) * (number of occurrences of complimentary sum(c,d)) to the result.

Creating sum(A, B) and sum(C, D) will take O(n^2) time. And counting the number of tuples is O(n^2) as there are n^2 sum for each pairs(A-B, C-D). Other operation like insertion and search on hashtable is amortized O(1). So, the overall time complexity is O(n^2).