Find all pairs of numbers whose sum is less than S

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?开发者_开发技巧

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.

This might help:

Find two no's in an array whose sum =X

David's solution should work. It will be O(N) even if there are more than N solutions.

1) Start with *ptr1 = a[0] and *ptr2 = a[X] <= S (X not always N-1)

2) Move ptr2 backwards until ptr1+ptr2 <= S.

-- at this point, ptr1 + all the indexes up to ptr2 are solutions.

3) Move ptr2 back one index, and move ptr1 up one index

-- repeat

Continue until ptr1 > ptr2

Enumerating all such pairs is already in O(n^2) (note, that this is different to the problem of summing up to exactly S, since in that case the enumeration can be done in O(n) like "3 times pair (w,x), 1 time pair (y,z), ..."

There is no O(n) solution. For example if you have a list like this: 1,2,3,4...n and S=3*n then every pairs sum is less than S. And the number of pairs that have to return is n*(n-1)/2.