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).

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

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

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).

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!

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).