An algorithm that checks if the arrays S and T are integers s and t, so s + t = k if k is given a number

Question

I am trying to make an algorithm that takes two arrays, S and T of n integers and integer k. The algorithm checks if the arrays have integers s and t, therefore s + t = k. (S to S and t to T). It is assumed that the algorithm has an O (n log n) runtime.

We tried to think of something that sorts the array T and use it for a loop to go through S and use a binary search to find out if I find an integer k - S [i] for each element from S. But this will always be done time is greater than n log n. I think so.

No one needs to write code. Just ask here to get some ideas.

Answer 1

Sorting two lists, this is O (n log n).

Then configure two iterators. One iterator starts with the smallest value in S and advances along constantly increasing values ​​in S. Another iterator starts with the highest value in T and iterates over constantly decreasing values.

Repeat the following:

• if the current values ​​add up to a number greater than k, advance the T-iterator. This should reduce the amount.
• if the current values ​​add up to a number less than k, advance the S-iterator. This should increase the amount.
• if the current values ​​are summed with k, then they exit successfully.

This second phase should cause, at most, 2N, and therefore O (n). So the overall complexity is O (n log n).

This has the same complexity as repeated binary searches, but this algorithm should be faster, especially for large n.

Answer 2

The algorithm you specified really has an O (n log n) runtime, assuming that the total number of elements in both arrays is O (n). You can see it here:

• Sort one of the arrays (O (n log n))
• For each element of another array: (O (n) iterations)
  • Do a binary search to see if there is an additional element in another array (time O (log n))

The first step takes O (n log n) time, and the second step consists of O (n) iterations of the O (log n) algorithm, which thus also takes O (n log n) time. Since O (n log n) + O (n log n) = O (n log n), your algorithm works in time O (n log n). So it looks like you have exactly the algorithm you are looking for!

Hope this helps!

Answer 3

Sort both arrays. Go through them in opposite directions. If the sum of these two elements is less than k, move the "increasing" pointer; if it is greater than k, draw a decreasing pointer. This method may be a little slower than sorting just one of the arrays, but the final pass is definitely faster. And probably shorter, because the head and tail of the two arrays can be skipped (shortened).

Answer 4

Your approach seems right; first sorting the arrays, two O (n log n) operations, and then you do n binary searches, which are O (log n) each.

Answer 5

Sort - O (n log n). Then for each element O (n) you have a search O (log n) of the corresponding element. This sounds like O (n log n) as a whole (since O (f) + O (f) = O (f) for any function f).

Answer 6

Another way: store one of the arrays in a hash table (O (N)). Draw a linear pass through the other (O (N)), and for each element, search for k-elem in the hash table. Total lead time: 2 * O (N): = O (N). Profit!