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)$?

  • 2
    $\begingroup$ The $k$-SUM problem usually refers a slightly different problem, where one tries to find a set of $k$ elements from the input array $A$ such that they sum to zero. In a certain model of computation, it is impossible to obtain a linear time algorithm for $k=2$, or for any even $k$. See this question. $\endgroup$
    – Juho
    Commented Aug 3, 2013 at 11:54

3 Answers 3


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$.

 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]) 

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

  • 4
    $\begingroup$ You should probably add an argument for correctness. $\endgroup$
    – Raphael
    Commented Aug 7, 2013 at 8:03

The simplest approach, by my understanding, seems to be to use a Hash-Table, H = {a[0] = true, .. , a[n-1] = true}. This Hash-Table can be built in O(n) time. Once the Hash-Table is built, iterate through A[0,..,n-1] and check if H[-1*a[i]] exists. If it does, increment a counter by 1, and return the final result. This is clearly O(n).

  • 3
    $\begingroup$ The expressions H = {a[0] = true, .. , a[n-1] = true} and A[0,..,n-1] don't make any sense to me. When using a hash function the array must not even be sorted. But algorithms using hash function uses some pseudorandom properties of hash function. In the worst case all items will map to the same hash value and the algorithm is quadratic. I don't know what are the requirements of the OP. $\endgroup$
    – miracle173
    Commented Jun 20, 2017 at 23:16
  • $\begingroup$ See my implementation of this below and tell me how it's quadratic in the worst case. $\endgroup$
    – sammy
    Commented Jun 21, 2017 at 2:15
  • $\begingroup$ @miracle173 : That's just convenience for notation. I can represent the Hash-Table as a set of Key-Value pairs (which is what it actually is, mathematically speaking). The actual arrangement in memory is unnecessary for theoretical details regarding complexity. And, Hash functions are designed to avoid collisions provided enough seed entropy. I replied with the because Juho 's answer assumes a "sorted A", which implicitly makes the complexity O(nlog(n)) and *NOT O(n). $\endgroup$ Commented Jun 21, 2017 at 5:18
  • $\begingroup$ @manbearpig1 User Evil already added a comment to your post that should answer your question. The worst case of the hash table lookup is O(n) and therefore the the worst case of the whole algorithm is O(n^2). $\endgroup$
    – miracle173
    Commented Jun 21, 2017 at 6:00
  • $\begingroup$ @JuspreetSandhu Usere Evil added a comment to an other answer that explained the problem with hash functions. $\endgroup$
    – miracle173
    Commented Jun 21, 2017 at 6:08

Note that we can lookup a value in a Python set in constant time.

def twoSum(data):
    count = 0
    nums = set()
    for num in data:
        if (num * -1) in nums:
            count += 1
    return count
  • 1
    $\begingroup$ It is not constant time but expected constant time. There might be hash table, a (self) balanced tree or similar sructure. This gives expected $\mathcal O(1)$ but it may be $\mathcal O(n)$ in degraded case for hash table or $\mathcal O(\log n)$ for tree. Besides here we prefer pseudocode because not everybody understands python, so it is not obvious why or how it works. In the worst case for the hash table where every value is mapped into one bin, the time to get element is $\mathcal O(n)$. You perform this step $n$ times so it gives $\mathcal O(n^2)$ in the worst case. $\endgroup$
    – Evil
    Commented Jun 21, 2017 at 4:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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