# Finding best three numbers of an array

Given a sorted array of $$n$$ integers ,and some other integer $$m$$, find the $$3$$ numbers in the array $$x,y,z$$ such that $$x+y+z\ge m$$,and their sum is minimal.

If there are no such,return null.

Any ideas for an efficient algorithm to find it?

• Do you have any ideas? What have you tried? Can you think of any algorithms at all? Did you try solving the variant with only two variables $x,y$? – Yuval Filmus Apr 25 '17 at 20:30
• Note that this problem is at least as hard as 3SUM (why?), if by "smallest 3 numbers" you mean that you want to minimize $x+y+z$ under the constraint $x+y+z \ge m$. – Yuval Filmus Apr 25 '17 at 20:31
• Obviously possible in $O(n^2)$ with any reasonable definition of "smallest 3 numbers". Possibly faster depending on definition of "smallest 3 numbers". – gnasher729 Apr 25 '17 at 20:39
• @YuvalFilmus It's not a HW question or such.I'm trying to implement some other algorithm,which I need to find those 3 numbers for that algorithm.I don't know how to do it.And yes,that's what I meant by smallest. – ChikChak Apr 25 '17 at 20:46
• It still seems unclear. Consider this array [1,2,3,4,5] and m=8. How do you want to compare [1,2,5] and [1,3,4]. Do you need all of them or just one of them will do the job? – Prateek Apr 25 '17 at 20:57

The algorithm for finding three number $x, y, z$ under the constraint $x+y+z \ge m$ can be extended from the idea of finding two numbers $x, y$ under a similar constraint $x+y \ge m$.

Initially we fix the value of $x = A_1$, first element of array. Next we will look for $y$ and $z$ in the subarray $A_2 ... A_n$. We repeat the above step by setting $x = A_2$ in the next iteration and look for $y$ and $z$ in the subarray $A_3 ... A_n$. We repeat this step until one of the following conditions are meet.

1. We find a triple $x, y, z$ such that $x + y + z = m$. As that is the minimum we have to look for, and you just need one of them.
2. We reach a point where we have set $x = A_{n-2}$ and looked for other two values in the second last and last element of the array i.e., the triple $<A_{n-2}, A_{n-1}, A_{n}>$

Also, there could be many triples in an array satisfying the condition $x+y+z \ge m$ and we need the one with the minimum sum. For this, we keep a separate copy of triple found so far under the specified condition and compare it everytime we find a new one.

Here is the pseudocode

FindTriple(A,n,m)
if A[n-2]+A[n-1]+A[n] < m
print "No solution"
return 0

#Set to some maximum value, for first time comparison
x = y = z = INFINITY

for i = 1 to n
j = i+1
k = n

while k>j
sum = A[i]+A[j]+A[k]

if sum == m
print <A[i],A[j],A[k]>
return 1
else if sum > m
if sum < (x+y+z)
<x,y,z> = <A[i],A[j],A[k]>
k=k-1
else j = j+1

print <x,y,z>


Runtime complexity of this algorithm is $O(n^2)$.

I took time answering this question because I was looking for an algorithm with better runtime complexity. Thanks to Yuval Filmus's answer that saved a lot of my time.

Here is the link to the working implementation of this algorithm in C language

• I think there is a typo in the first line of code in findTriple(). The middle term of the first expression in the if statement should be a[n-1]. – Rich Holton Apr 27 '17 at 0:50
• @RichHolton Thank you for pointing that out. I have fixed it. – Prateek Apr 27 '17 at 4:36

You can solve this in $O(n^2\log n)$ in the following way:

1. Construct and sort the list consisting of all sums $x + y$.
2. Go over all $z$, and for each them find the minimal $x+y \geq m-z$ using binary search.

It is very likely that this can be improved to $O(n^2)$ by adapting the 3SUM quadratic algorithm.

On the other hand, you can clearly solve 3SUM given a solution to your problem (just check whether $x+y+z=m$), making it 3SUM-hard to improve $O(n^2)$ to $O(n^{2-\epsilon})$ for any $\epsilon > 0$. (That is, the 3SUM conjecture implies that no $O(n^{2-\epsilon})$ algorithms exist.)

• How can I modify the quadratic algorithm to work in this case aswell? The problem with it that this algorithm looks only for 3 numbers so thier sum will be exactly , when I allow it to be "a bit" more as well.. – ChikChak Apr 25 '17 at 21:26
• Unfortunately I am not willing to answer this question. You'll have to figure out the required modification (if it is at all possible) on your own. – Yuval Filmus Apr 25 '17 at 21:29
• But is it even possible? – ChikChak Apr 25 '17 at 21:35
• I don't know, but it seems likely. – Yuval Filmus Apr 25 '17 at 22:03

Not getting the down votes so I wrote a program to test.

a, b, c are the indexes
a < b < c

m is target

Where this differs from the accepted solution is for each a, a+1 it does a binary search for the c rather than walk it down. And it gives up if a + the last two (biggest) are < sum. This shifts it towards $O(n log n)$ but worst case it is still $O(n * n)$.

1. a = 0, b = 1
2. perform a binary search on c
3. if sum = m then done
4. if sum > target then c-- else b++
6. if c == b then a++ b=a+1 go to 2
7. goto 3

I think this is close to $O(n log n)$

public static int BinarySearch(int[] A, int T, int? l, int? r)
{
// Given an array A of n elements with values or records A0 ... An−1, sorted such that A0 ≤ ... ≤ An−1, and target value T, the following subroutine uses binary search to find the index of T in A.
// 1. Set L to 0 and R to n − 1.
// 2. If L > R, the search terminates as unsuccessful.
// 3. Set m(the position of the middle element) to the floor of (L + R) / 2.
// 4. If Am < T, set L to m + 1 and go to step 2.
// 5. If Am > T, set R to m – 1 and go to step 2.
// 6. Now Am = T, the search is done; return m.
Array.Sort(A);
int M = -1;
int L = l == null ? 0            : (int)l;
int R = r == null ? A.Length - 1 : (int)r;
while (L <= R)
{
M = (L + R) / 2;
if (A[M] < T) L = M + 1;
else if (A[M] > T) R = M - 1;
else return M;
}
return M;
}
public static int BinarySearchList(List<int> A, int T, int? l, int? r)
{
// Given an array A of n elements with values or records A0 ... An−1, sorted such that A0 ≤ ... ≤ An−1, and target value T, the following subroutine uses binary search to find the index of T in A.
// 1. Set L to 0 and R to n − 1.
// 2. If L > R, the search terminates as unsuccessful.
// 3. Set m(the position of the middle element) to the floor of (L + R) / 2.
// 4. If Am < T, set L to m + 1 and go to step 2.
// 5. If Am > T, set R to m – 1 and go to step 2.
// 6. Now Am = T, the search is done; return m.

int M = -1;
int L = l == null ? 0 : (int)l;
int R = r == null ? A.Count() - 1 : (int)r;
while (L <= R)
{
M = (L + R) / 2;
if (A[M] < T) L = M + 1;
else if (A[M] > T) R = M - 1;
else return M;
}
return M;
}
public static List<int> Sum3(List<int> input, int sum)
{
//a,b,c are index to input
//start a = 0, b = 1 and solve for c
//reduce c until under
//when b=c the a++ b=a+1

if (input.Count() < 3)
throw new ArgumentOutOfRangeException();
//is it sorted
int? iLast = null;
for (int i = 0; i < input.Count(); i++)
{
if (iLast != null && i <= iLast)
throw new ArgumentOutOfRangeException();
iLast = i;
}
if (input + input + input > sum)
throw new ArgumentOutOfRangeException();
if (input[input.Count() - 1] + input[input.Count() - 2] + input[input.Count() - 3] < sum)
throw new ArgumentOutOfRangeException();

int a = -1;
int b = -1;
int c = 2;
int currentSum;
int? lastC = null;
int count = 0;
for (a = 0; a < input.Count() - 2; a++)
{
count++;
if (input[a] + input[input.Count() - 1] + input[input.Count() - 2] < sum)
continue;
if (input[a] + input[a + 1] + input[a + 2] > sum)
break;
b = a + 1;
c = BinarySearchList(input, sum - input[a] - input[b], b + 1, lastC);
lastC = c;
while(c > b)
{
currentSum = input[a] + input[b] + input[c];
if (currentSum == sum)
return new List<int> { a, b, c };
if (currentSum < sum)
b++;
else
c--;
}
}
return null;
}

• Care to explain why it works and why you think it's $O(n\log n)$? As I'm pretty sure we've said to you before, we're looking for full answers, not just (pseudo-)code dumps. – David Richerby Apr 26 '17 at 20:29
• @DavidRicherby You make n moves and one log lookup for each move. Actually worse case (n-2) log((n-2)/2) – paparazzo Apr 26 '17 at 21:13