Ali Mohsin - 6 months ago 68

C# 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 -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)`

.