Find all pairs of numbers whose sum is less than S

Question

Given a sorted array a[0...n-1], find all pairs of numbers whose sum is less than S. Is there an O(n) solution?

Answer 1

Are you in the interview right now? Are they returning to the room soon?

Since it's sorted, then one of the solutions (if any!) is [0] and some highest [M]. Then work the lower index upwards from 0, and the upper index downwards from M. And some details about which to bump and when to reject.

Edit -- since there could still be O(n^2) solutions (for example if S is more than twice as large as the biggest entry), a trick will be to express the solutions as ranges. Otherwise, just the enumeration will take too long.