Ali Mohsin Ali Mohsin - 15 days ago 10
C# Question

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

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 -228 to 228 - 1
and the result is guaranteed to be at most 231 - 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

I suggest kind a 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] 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
        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).