Find all pairs (x, y) in a sorted array so that x + y <z

Question

This is an interview question. Given that the sorted integer array and the number z determine all the pairs (x, y) in the array, so x + y <r. Can this be done better than O (n ^ 2)?

PS I know that we can find all the pairs (x, y | x + y == z) in O (N).

Answer 1

You cannot find all such pairs in O (n ² ) time, because there may be O (n ² ) pairs that have this property. In general, an algorithm cannot take less time to start than the number of generated values.

Hope this helps!

Answer 2

In generation, no, he cannot. Consider the case where x + y < z for all x , y in the array. You must touch (for example, the map) all possible n(n - 1)/2 possible pairs in the set. This is basically O (n ^ 2).

Answer 3

If you are asked to output all pairs that satisfy this property, I do not think that there is anything better than O (N ^ 2), since there may be O (N ^ 2) pairs at the output.

But this is also true for x + y = z, for which you are claiming that there is an O (N) solution, so I might be missing something.

I suspect the original question asked the number of pairs. In this case, this can be done in O (N log (N)). For each element x, find y = z - x and do a binary search of y in the array. The y position gives the number of pairs that can be formed with this particular x value. Summing this over all the values ​​in the array, you will get the answer. There are N values ​​and a number search if the pairs for each take O (log (N)) (binary search), so all this is O (N log (N)).

Answer 4

You can find them in O (N) if you add an extra constraint so that each element is unique.

After finding all the pairs x + y == z, you know that for every x and y satisfying this condition, every x or y (choose one) that has a lower index than its pair satisfies x + y <z.

In fact, choosing these and deducing them will take O (n ^ 2), but in a sense, the pairs x + y == z are a compressed form of the answer along with the input.

(You can pre-process the input to the form where each element is unique, together with a counter for the number of entries. It will take O (N) time. You can generalize this solution to unsorted arrays by increasing the time to O (NlogN).)

The rationale for finding pairs over a time linearly proportional to the size of the solution: Suppose the question is, "What are integers between 0 and given input K"?

Answer 5

Since this is an array with a sorted integer, you can use a search algorithm therefore O(N) best, and the worst is O(N*logN) , the average case is also O(N*logN) .

Answer 6

You can sort the array and for each element that is smaller than z, use a binary search - generic O (NlogN).

Total execution time: O (| P | + NlogN), where P are the received pairs.

Answer 7

Actually there is an O (nlogn) solution for this question. What I would do (after checking first, if I allow it) is to determine the output format of my algorithm / function.

I would define it as a sequence of elements (S, T). S - The position of the element in the array (or its value). T is the position of the submatrix [0, T]. So, for example, if T = 3, this means that the element S combined with elements 0,1,2 and 3 satisfies the desired condition.

The result of this is O (nlogn) runtime and O (n) memory.