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

Question

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

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

Answer 1

You cannot necessarily find all such pairs in O(n) time, because there might be O(n²) pairs of values that have this property. In general, an algorithm can't take any less time to run than the number of values that it produces.

Hope this helps!

Answer 2

In generate, no it can't. Consider the case where x + y < z for all x, y in the array. You have to touch (e.g. display) all of the n(n - 1)/2 possible pairs in the set. This is fundamentally O(n^2).