8
$\begingroup$

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

$\endgroup$
  • 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 Aug 3 '13 at 11:54
12
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ You should probably add an argument for correctness. $\endgroup$ – Raphael Aug 7 '13 at 8:03
-1
$\begingroup$

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

$\endgroup$
  • 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 Jun 20 '17 at 23:16
  • $\begingroup$ See my implementation of this below and tell me how it's quadratic in the worst case. $\endgroup$ – manbearpig1 Jun 21 '17 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$ – Juspreet Sandhu Jun 21 '17 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 Jun 21 '17 at 6:00
  • $\begingroup$ @JuspreetSandhu Usere Evil added a comment to an other answer that explained the problem with hash functions. $\endgroup$ – miracle173 Jun 21 '17 at 6:08
-1
$\begingroup$

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
        nums.add(num)
    return count
$\endgroup$
  • 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 Jun 21 '17 at 4:03

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.