Suppose we have two sorted arrays: A and B of size n.
We would like to know if there is such a pair of indexes (i,j) that A[i] + B[j] = C.
C is a given number.
What’s the best worst-case time complexity (Big Oh) of the algorithm to solve the problem?
-
Photo
More Photos 
We read- Identifying almost identical files using context triggered piecewise hashing
- software - xml - s-exp vs XML | cat -v harmful stuff
- Why? Language Archaeology ... and Metaprogramming
- Emacs key bindings in Mac OS application.
- SICP Wiki
- CS193P - Cocoa Programming | iPhone application programming (Stanford)
- How to Write an Equality Method in Java
- A Beautiful Race Condition
- Grant Rettke: A Card Stack Handheld UI Approach
- 18 Useful bash scripts for web developers
8 Comments
Hm. At first sight it is O(n*log(n)). But probably I’m wrong and there is O(n) solution.
Nikolay: Yes, that’s the first solution that comes to mind:
for i in A:
search(C – A[i]) in B
But… ;)
it looks like you have to pass each array only once, but at the same time and in different directions.
so Nikolay was right, there is a O(n) solution :)
p.s. i wonder if html tags work here invisible text
nope, html tags don’t work here :)
Aram: You’re right. There is O(n) solution :)
There is an obvious O(n) solution if you have infinite memory and numbers are integers :)
Damn!!! Arrays are sorted!!!!
That is really obvious then!!!
Actually, the merge sort algorithm exploits the same idea. Its ‘merge’ part takes an input of several sorted arrays and must choose, on which of them to step forward.
In this puzzle the tricky part is to process one of the arrays in the reversed order.
Here’s the puzzle from the same domain: “You have three sorted arrays and required to find a triplet of elements from each array having the minimum distance between them. Distance is calculated as max(|a[i] – b[j]|, |a[i] – c[k]|, |b[j] – c[k]|). The algorithm must have linear time complexity and constant space complexity”.