How to develop an $O(N)$ algorithm solve the 2-sum problem?

Problem Detail: 

Given an sorted array of integers, I want to find the number of pairs that sum to $0$. For example, given $\{-3,-2,0,2,3,4\}$, the number of pairs sum to zero is $2$.

Let $N$ be the number of elements in the input array. If I use binary search to find the additive inverse for an element in the array, the order is $O(\log N)$. If I traverse all the elements in the set, then the order is $O(N\log N)$.

How to find an algorithm which is of order $O(N)$?

Asked By : Laura

Answered By : Juho

Let $A$ be the sorted input array. Keep two pointers $l$ and $r$ that go through the elements in $A$. The pointer $l$ will go through the "left part" of $A$, that is the negative integers. The pointer $r$ does the same for the "right part", the positive integers. Below, I will outline a pseudocode solution and assume that $0 \notin A$ for minor simplicity. Omitted are also the checks for the cases where there are only positive or only negative integers in $A$.

COUNT-PAIRS(A[1..N]):  l = index of the last negative integer in A  r = index of the first positive integer in A  count = 0;   while(l >= 0 and r <= N)    if(A[l] + A[r] == 0)      ++count; ++right; --left; continue;     if(A[r] > -1 * A[l])       --left;    else       ++right; 

It is obvious the algorithm takes $O(N)$ time.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13585