Take the 2-minute tour ×

Assume we have three arrays of length N which contain arbitrary numbers of type long. Then we are given a number M (of the same type) and our mission is to pick three numbers A, B and C one from each array (in other words A should be picked from first array, B from second one and C from third) so the sum A + B + C = M.

Question: could we pick all three numbers and end up with time complexity of O(N2)?


Arrays are:

1) 6 5 8 3 9 2
2) 1 9 0 4 6 4
3) 7 8 1 5 4 3

And M we've been given is 19. Then our choice would be 8 from first, 4 from second and 7 from third.

share|improve this question
Why is there a c++ tag? –  Matthijs Wessels Oct 21 '10 at 12:51
A job offer was "C++ programmer" and that is all in fact. –  Keynslug Oct 21 '10 at 12:58
I removed the C++ tag –  CashCow Oct 21 '10 at 13:30
add comment

11 Answers 11

up vote 143 down vote accepted

This can be done in O(1) space and O(N2) time.

First lets solve a simpler problem:
Given two arrays A and B pick one element from each so that their sum is equal to given number K.

Sort both the arrays which takes O(NlogN).
Take pointers i and j so that i points to the start of the array A and j points to the end of B.
Find the sum A[i] + B[j] and compare it with K

  • if A[i] + B[j] == K we have found the pair A[i] and B[j]
  • if A[i] + B[j] < K, we need to increase the sum, so increment i.
  • if A[i] + B[j] > K, we need to decrease the sum, so decrement j.

This process of finding the pair after sorting takes O(N).

Now lets take the original problem. We've got a third array now call it C.

So the algorithm now is :

foreach element x in C
  find a pair A[i], B[j] from A and B such that A[i] + B[j] = K - x
end for

The outer loop runs N times and for each run we do a O(N) operation making the entire algorithm O(N2).

share|improve this answer
+1, Beautiful explanation. –  aioobe Oct 21 '10 at 12:31
Great! i had bet the sorting was the point. –  Keynslug Oct 21 '10 at 12:54
Regarding the part where you walk i and j towards each other: I seem to recall this is correct, but you need to explain why, because some element pairs are not examined during this process: e.g. if you increase i twice at the start, then decrease j twice, the pair (initial_i+1, initial_j-1) is never checked. One (sufficient but not necessary) way would be to prove that any skipped-over element pairs cannot possibly sum to K. –  j_random_hacker Oct 22 '10 at 4:05
At first iteration, if A[i] + B[j] < K it means that we need to increment one of the number but because B is sorted and j is at the last element of B yielding the maximum number in B thus the only possible way to continue is by incrementing i to try out the next biggest number. -- if A[i] + B[j] > K it means that we need to decrement one of the number but because A is sorted and i is at the first element of A yielding the minimum value possible from A, the only possible way to continue is by decrementing j to try out the next smallest number. -- cont. w/ induction. –  chakrit Oct 22 '10 at 5:43
I'm -1ing until correctness of this part of the algorithm is shown. (As I said I believe it is correct, but I want to see it proven!) –  j_random_hacker Oct 23 '10 at 12:29
show 16 more comments

You can reduce it to the similar problem with two arrays, which is kinda famous and has simple O(n) solution (involving iterating from both ends).

  1. Sort all arrays.
  2. Try each number A from the first array once.
  3. Find if the last two arrays can give us numbers B and C, such that B + C = M - A.

Steps 2 and 3 multiplied give us O(n^2) complexity.

share|improve this answer
Nice to see another person thinking on exact same lines :) –  codaddict Oct 21 '10 at 12:28
No need to sort the first array, otherwise perfect solution. –  Ben Voigt Oct 21 '10 at 12:30
@codaddict nice explanation, btw! I've spent 10 minutes searching for any other questions with that problem to link, but no luck. –  Nikita Rybak Oct 21 '10 at 12:37
@Ben Aaarg, who cares, it's only nlogn :) But you're right, of course: no need to do that in the code. –  Nikita Rybak Oct 21 '10 at 12:38
add comment

The other solutions are already better, but here's my O(n^2) time and O(n) memory solution anyway.

Insert all elements of array C into a hashtable. (time complexity O(n), space O(n)) Take all pairs (a,b), a from A and b from B (time complexity O(n^2)). For each pair, check if M-(a+b) exists in the hastable (complexity O(1) expected per query).

So, the overall time complexity is O(n^2), and a space complexity of O(n) for the hashtable.

share|improve this answer
You meant to check if M-a-b exists in the hashtable, did not you? –  Keynslug Oct 21 '10 at 13:02
@Keynslug: Yes. Thanks for pointing that out, I've corrected my answer. –  MAK Oct 21 '10 at 13:12
add comment

Hash the last list. The time taken to do this is O(N) on that particular list but this will be added to the next phase.

The next phase is to create a "matrix" of the first two rows of their sums. Then look up in the hash if their matching number is there. Creating the matrix is O(N*N) whilst looking up in the hash is constant time.

share|improve this answer
add comment

1.Store A[i]*B[j] for all pair (i,j) in another array D, organized in the hash data-structure. The complexity of this step is O(N*N).

construct a hash named D
for i = 1 to n
    for j = 1 to n
        insert A[i]*B[j] into D

2.For each C[i] in the array C, find if M-C[i] exists in D. The complexity of this step is O(N).

for i = 1 to n
    check if M - C[i] is in D
share|improve this answer
I think you mean A[i]+B[j], not A[i]*B[j]. But very clever! –  MatrixFrog Jul 13 '11 at 10:01
add comment

I have a solution. Insert all elements from one of the list into a hash table. This will not take O(n) time.

Once that is complete you find all the pairs from the remaining 2 arrays and see if their sum is present in the hash table.

Because hash hookup is constant we get a quadratic time in total.

Using this approach you save the time on sorting.

Another idea is if you know the max size of each element, you can use a variation of bucket sort and do it in nlogn time.

share|improve this answer
add comment

At the cost of O(N^2) space, but still using O(N^2) time, one could handle four arrays, by computing all possible sums from the first two arrays, and all possible residues from the last two, sort the lists (possible in linear time since they are all of type 'long', whose number of bits is independent of N), and then seeing if any sum equals any residue.

share|improve this answer
Well, you could just hash the residues (or the sums) in O(N^2) time and space, then look up (in O(N^2) time) all the sums (or residues). –  Neil Oct 23 '11 at 20:27
My point was that one is if one is going to have to perform some operation on an NxN cross-join of array elements, one may as well--at least from an O() perspective, perform two cross-joins. Your mention of hashes got me thinking, though: what about partitioning based upon lower bits? If we divide the lists of size n into k=2^b partitions based upon the b lower bits, then for any pair of partitions taken from any two of the lists, on will only have to look in a single partition of the third. –  supercat Oct 23 '11 at 23:48
Yes, I understood the double cross-join, which is why I gave you an upvote, but I wanted to suggest that hashing might be superior to sorting. Off the top of my head I don't see the point of multiple hashes though. –  Neil Oct 24 '11 at 22:58
add comment

Sorting all 3 arrays and using binary search seems a better approach. Once the arrays are sorted, one should definitely go for binary search rather than linear search, which take n rather than log(n).

Hash table is also a viable option.

The combination of hash and sort can bring the time down but at cost of O(N square) space.

share|improve this answer
add comment

I have another O(N^2) time complexity, O(N) additional space complexity solution.

First, sort the three arrays, this step is O(N*log(N)). Then, for each element in A, create two arrays V = Ai + B and W = Ai + C (Ai is the current element). Ai + B means that each element of this new array V is the elemnent in that position in B plus Ai(the current element in A). W = Ai + C is similar.

Now, merge V and W, as in merge sort. Since both are sorted, this is O(N). In this new array with 2*N elements, search for M + Ai(because Ai is used twice). This can be done in O(log n) with binary search.

Therefore, total complexity is O(N^2).

share|improve this answer
add comment

Sort the three arrays.Then initialize three indices

  1. i pointing to first element of A,
  2. j pointing to last element of B and
  3. k pointing to first element of C. While i,j,k are in the limits of their respective arrays A,B,C

  4. If A[i]+B[j]+C[k] == M return

  5. If A[i]+B[j]+C[k] < M .Increment i if A[i]<=C[k] otherwise increment k.

  6. If A[i]+B[j]+C[k] > M. Decrement j.

Which should run in O(n).

share|improve this answer
add comment

How about:

for a in A
 for b in B
  hash a*b

for c in C
 if K-c is in hash
   print a b c

The idea is to hash all possible pairs in A and B. Next for every element in C see if the residual zum is present in hash.

share|improve this answer
add comment

Your Answer


