Determine whether 4 elements in an array sum to 0 in O(n^2) time.

Question

MJ · Accepted Answer

Yeah, it's impossible to do it O(n^2) worst case, but very possible O(n^2) average case. Here:

1. Hash the sum of all pairs -> O(n^2) average // be sure to store the indices to avoid double counting.
2. Now just go through the original list, and for each pair of elements, check if a non intersecting -sum is found in the hash table from part 1. -> O(n^2) average.

In case it is not obvious why 2 is O(n^2) despite the fact that we are "searching" for Non-Intersecting sums, you should convince yourself that even if all pairs sum to a specific number, you will only need to check a constant number of elements. (hint: grid)

Anon · Answer

Create a dict k. 

For each two elements i and j (i≠j) of array arr, set k[arr[i]+arr[j]]=min(j, k[arr[i]+arr[j]]).

Iterate again: for each i and j, check if k[-(arr[i]+arr[j])] exists and is less then j. If so, print yes. 

If you reach the end of the loop, print no.

Sigiloso · Answer

Let N be the size of the array. There will be N!/(N-2)!.2! pairs possible. (excluding the repeating ones)
Create a new array with size M=N!/(N-2)!.2! of structs/class (int x, int y and int sum as fields)
Each element in the new array is the sum of each possible pair from first array along with indices (store i & j of iteration in x & y ).  Complexity - O(n^2)
Again find the sum of each pair excluding the matching indexes (using struct's x & y field) to find the sum that equal 0. If 0 print the indexes. O(n^2).

Overall complexity O(n^2).

SingleStore

Pergunta de entrevista da empresa SingleStore

Respostas da entrevista

Empresas seguidas

Buscas de vagas