Question from the interview: three arrays and O (N * N)

Question

Suppose we have three arrays of length N that contain arbitrary numbers of type long . Then we are assigned a number M (of the same type), and our task is to select three numbers A , B and C from one of each array (in other words, A must be selected from the first array, B from the second and C from the third) therefore, the sum A + B + C = M.

Question: can all three numbers be selected and eventually run O (N ² ) over time?

---

Illustration:

Arrays:

 1) 6 5 8 3 9 2 2) 1 9 0 4 6 4 3) 7 8 1 5 4 3 

And M was given to us 19. Then our choice will consist of 8 first, 4 from the second and 7 from the third.

Answer 1

This can be done in O (1) space and O (N ² ) time.

First, let's solve a simpler problem:
For two arrays A and B select one element from each so that their sum is equal to the given number K

Sort both arrays that accept O (NlogN).
Move the pointers i and j so that i points to the beginning of array A and j points to the end of B
Find the sum A[i] + B[j] and compare it with K

• if A[i] + B[j] == K we found a pair of A[i] and B[j]
• if A[i] + B[j] < K , we need to increase the amount, therefore the increment i .
• if A[i] + B[j] > K , we need to reduce the amount, so decrement j .

This process of finding a pair after sorting takes O (N).

Now let's take the original task. Now we have the third array of C

So now the algorithm:

 foreach element x in C find a pair A[i], B[j] from A and B such that A[i] + B[j] = K - x end for 

The outer loop starts N times, and for each run we perform the operation O (N), which makes the whole algorithm O (N ² ).

Answer 2

You can reduce it to a similar problem with two arrays, which is known and has a simple O (n) solution (using iteration from both ends).

• Sort all arrays.
• Try each number A from the first array once.
• Find if the last two arrays can give us numbers B and C , such that B + C = M - A

Steps 2 and 3 multiply the complexity of O (n ^ 2).

Answer 3

Other solutions are already better, but here is my O (n ^ 2) time and O (n) memory solution anyway.

Insert all the elements of array C into the hash table. (time complexity O (n), space O (n)) Take all pairs (a, b), a from A and b from B (time complexity O (n ^ 2)). For each pair, check if M- (a + b) exists in hastable (O (1) complexity expected for each request).

So the total time complexity is O (n ^ 2) and the spatial complexity is O (n) for the hash table.

Answer 4

Hash the last list. The time spent on this is O (N) in this particular list, but it will be added to the next phase.

The next step is to create a “matrix” of the first two rows of their sums. Then find the hash, if their corresponding number is. Creating a matrix is ​​O (N * N), and searching in a hash is a constant time.

Answer 5

I have a solution. Paste all the items from one of the list into the hash table. It does not take O (n) time.

Once this is completed, you will find all the pairs from the remaining 2 arrays and see if their sum is present in the hash table.

Since the hash is constant, we get the quadratic time.

Using this approach, you save time when sorting.

Another idea: if you know the maximum size of each element, you can use the bucket sort variation and do it at nlogn time.

Answer 6

1. Store A [i] * B [j] for all pairs (i, j) in another array D, organized in a hash data structure. The complexity of this step is O (N * N).

 construct a hash named D for i = 1 to n for j = 1 to n insert A[i]*B[j] into D 

2. For each C [i] in array C, find if MC [i] exists in D. The complexity of this step is O (N).

 for i = 1 to n check if M - C[i] is in D 

Answer 7

Due to the space O (N ^ 2), but using O (N ^ 2) time, you can process the four arrays, calculating all possible sums from the first two arrays, and all possible residues from the last two, sort the lists (possibly in linear time, since they are all of type "long", the number of bits of which does not depend on N), and then seeing if any sum is equal to any remainder.

Answer 8

Sorting all 3 arrays and using binary search is the best approach. After sorting the arrays, you must always look for a binary search, not a linear search, which takes n, not log (n).

A hash table is also a viable option.

The combination of hashes and sorting can lead to a reduction in time, but at the cost of space O (N square).

Answer 9

I have one more time complexity O(N^2) , O(N) an additional solution for spatial complexity.

First sort the three arrays, this step is O(N*log(N)) . Then, for each element from A create two arrays V = Ai + B and W = Ai + C ( Ai is the current element). Ai + B means that each element of this new array V is an element at this position in B plus Ai (current element in A ). W = Ai + C similar.

Now merge V and W , as in a merge sort. Since both are sorted, this is O(N) . In this new array with 2*N elements, find M + Ai (because Ai used twice). This can be done in O(log n) with binary search.

Therefore, the total complexity is O(N^2) .

Answer 10

Sorting three arrays. Then initialize the three indexes

• i pointing to the first element of A,
• j indicating the last element of B and

• k pointing to the first element of C. Although i, j, k are within their respective arrays A, B, C

• If A [i] + B [j] + C [k] == M return

• If A [i] + B [j] + C [k] M.Increment i, if A [i] <= C [k] otherwise, increment k.

• If A [i] + B [j] + C [k]> M. Decrement j.

which should work in O (n).

Answer 11

What about:

 for a in A for b in B hash a*b for c in C if Kc is in hash print abc 

The idea is to hash all possible pairs in A and B. Further for each element in C it follows if the residual zum is present in the hash.