Finding a sub-array where every pair has sum greater than a given K

Question

I have been given an array A of integers. Now I have to found out a sub-array(a sub-sequence of original array) where sum of every pair is greater than or equal to a pre-defined K.

What I thought :-

• Will sort the array in O(nlgn) or O(n) depending upon range of values in array.
• Find out i in sorted array such that sorted[i] + sorted[i+1]>=k
• Set max to sorted[i]
• Traverse the original array to delete all value smaller than max, which is the required sub-sequence

Repeat the above for all the elements of the array.

Running Time :- O(nlgn)

Is the solution optimal ? Can we further improve it ?

Example :-

-10 -100 5 2 4 7 10 23 81 5 25

Sorted Array

-100 -10 2 4 5 5 7 10 23 25 81

Let K = 20

Sub Array : -

10 23 25 81

Had the question been to find out longest sub-array, algorithm suggested by alestanis in the answers would work fine :)

Answer 1

Here is a fairly simple solution.

>>> def f(A, k):
...     solution = [item for item in A if 2*item >= k]
...     m = min(solution)
...     for item in A:
...         if item + m >= k and 2*item < k:
...             solution.append(item)
...             break
...     return solution
...
>>> f([-10, -100, 5, 2, 4, 7, 10, 23, 81, 5, 25], 20)
[10, 23, 81, 25]
>>>