2
$\begingroup$

In a sorted array, I am trying to find just one pair that sum up to a certain value. I was wondering if anyone could help me improve my code in performance or memory. I know the code which is $O(n)$. If there are other method for finding pairs the sum up to a certain value that is much more efficient.

I was asked this in an interview recently and interviewer told me that there exists a solution with $O(\log n)$ time complexity. Any ideas are appreciated.

$\endgroup$
3
  • $\begingroup$ Average or worst case? $\endgroup$ – Andris Birkmanis Dec 17 '20 at 21:01
  • $\begingroup$ He specifically mentioned worst case. How would I do it in O(Log n) in average case. $\endgroup$ – ABHIJEET SHUKLA Dec 18 '20 at 4:22
  • $\begingroup$ Just to clarify, as I believe the accepted answer is only applicable to disprove the existence of O(log n) worst case. $\endgroup$ – Andris Birkmanis Dec 19 '20 at 2:34
2
$\begingroup$

Your interviewer is wrong.

Suppose that you had an algorithm which gets as input a sorted integer array $A_1,\ldots,A_n$, outputs Yes iff $A_i + A_j = 0$ for some $i \neq j$, and always accesses at most $n-1$ inputs.

Suppose first that $n = 2m$ is even, and consider the following sorted integer array $B$: $$ -2m, -2(m-1), \ldots, -4, -2, 1, 3, \ldots, 2(m-1)-1, 2m-1. $$ This array contains no solution to $B_i + B_j = 0$. For any index $i$, we can create a sorted integer array $B^{(k)}$, differing only in the $k$'th entry, which does have a solution to $B^{(k)}_i + B^{(k)}_j = 0$.

Now run the given algorithm. Whenever it tries to access a position $A_i$, answer the value $B_i$. By assumption, the array terminates without querying some position, say $A_k$. Therefore the algorithm behaves the same when given as input the arrays $B$ and $B^{(k)}$, although the answer is No for the first one and Yes for the second one.

When $n=2m+1$ is odd, a similar argument works with the following sorted integer array: $$ -2m, -2(m-1), \ldots, -4, -2, 1, 3, \ldots, 2(m-1)-1, 2m-1, 2m+1. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.