Have O(n^2) algorithm for "two-sum", convert to O(n) linear solution

Question

I have an O(n^2) solution to the classic two-sum problem. Where A[1...n] sorted array of positive integers. t is some positive integer.

Need to show that A contains two distinct elements a and b s.t. a+ b = t

Here is my solution so far:

t = a number;
    for (i=0; i<A.length; i++)
          for each A[j]
            if A[i] + A[j] == t
                return true
    return false

How do I make this a linear solution? O(n) scratching my head trying to figure it out.

Here's an approach I have in mind so far. i will start at the beginning of A, j will start at the end of A. i will increment, j will decrement. So I'll have two counter variables in the for loop, i & j.

If the array is sorted: Put a pointer in the beguining, another pointer in the end. The first goes forward and the another goes backwards. — amchacon, Apr 16 '17 at 20:10
The array is sorted, I just added an approach where I use two counters, one goes forward, and the other goes backward. The length of A is arbitrary. Just say we can do A[10] for example — J. Don, Apr 16 '17 at 20:16
This is not a duplicate because the array is guaranteed to be sorted. — user202729, May 12 '18 at 04:43

score 2 · Answer 1 · answered Apr 16 '17 at 20:32

There are couple of ways to improve upon that.

You could extend your algorithm, but instead of doing a simple search for every term, you could do a binary search

t = a number
for (i = 0; i < A.length; i++)
  j = binarySearch(A, t - A[i], i, A.length - 1)
  if (j != null) 
      return true
return false

Binary search is done by O(log N) steps, since you perform a binary search per every element in the array, the complexity of the whole algorithm would be O(N*log N) This already is a tremendous improvement upon O(N^2), but you can do better.

Let's take the sum 11 and the array 1, 3, 4, 8, 9 for example. You can already see that (3,8) satisfy the sum. To find that, imagine having two pointers, once pointing at the beginning of the array (1), we'll call it H and denote it with bold and another one pointing at the end of the array (9), we'll call it T and denote it with emphasis.

1 3 4 8 9

Right now the sum of the two pointers is 1 + 9 = 10. 10 is less than the desired sum (11), there is no way to reach the desired sum by moving the T pointer, so we'll move the H pointer right:

1 3 4 8 9

3 + 9 = 12 which is greater than the desired sum, there is no way to reach the desired sum by moving the H pointer, moving it right will further increase the sum, moving it left bring us to the initital state, so we'll move the T pointer left:

1 3 4 8 9

3 + 8 = 11 <-- this is the desired sum, we're done.

So the rules of the algorithm consist of moving the H pointer left or moving the T pointer right, we're finished when the sum of the two pointer is equal to the desired sum, or H and T crossed (T became less than H).

t = a number
H = 0
T = A.length - 1
S = -1

while H < T && S != t
    S = A[H] + A[T]
    if S < t
        H++
    else if S > t
        T--

return S == t

It's easy to see that this algorithm runs at O(N) because we traverse each element at most once.

score 0 · Answer 2 · answered Apr 16 '17 at 20:12

0

You make 2 new variables that contain index 0 and index n-1, let's call them i and j respectively. Then, you check the sum of A[i] and A[j] and if the sum is smaller than t, then increment i (the lower index), and if it is bigger then decrement j (the higher index). continue until you either find i and j such that A[i] + A[j] = t so you return true, or j <= i, and you return false.

int i = 0, j = n-1;
while(i < j) {
    if(A[i] + A[j] == t)
        return true;
    if(A[i] + A[j] < t)
        i++;
    else
        j--;
return false;

answered Apr 16 '17 at 20:12

Meccano

537
4
8

If there a way to do this using a for loop, and shorten it? – J. Don Apr 16 '17 at 20:18
I can't find an implementation using a for loop that shortens it in any way. – Meccano Apr 16 '17 at 20:21

score 0 · Answer 3 · answered Apr 16 '17 at 20:17

Given that A[i] is relatively small (maybe less than 10^6), you can create an array B of size 10^6 with each value equal to 0. Then apply the following algorithm:

for i in 1...N:
    B[A[i]] += 1
for i in 1...N:
    if t - A[i] > 0:
        if B[t-A[i]] > 0:
            return True

Edit: well, now that we know that the array is sorted, it may be wiser to find another algorithm. I'll leave the answer here since it still applies to a certain class of related problems.

Have O(n^2) algorithm for "two-sum", convert to O(n) linear solution

3 Answers3

Linked