Ali Mohsin - 1 year ago 156
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++)
{
}
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.

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)`.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download