Checking if there are 2 elements in an array that sum to X in O(n lg n)

Question

I have thought about the most useful way of checking an array for 2 elements that sum to X. The trivial solution is to check the sum of every element with every element, and the complexity of this solution is $O(n^2)$.

My solution is: Say the array is A. It's length is N. Elements are from A[0] to A[N-1]

Pseudo-Code is:

Check_Sum(A,left,right) {
  mid <-- floor( (left+right)/2 )

  if(A[left]+A[right]=X)
    return true

  return Check_Sum(A,left,mid)||Check_Sum(A,mid,Right)
}

My question is: Is the complexity of my solution equal to $O(n \lg n)$?

Answer 1

Sort the array say ascending order- Takes O(nlogn)

Keep two pointers in the array say fingers. Finger f1 at the first element and finger f2 at the last element.

Sum the elements to get f1+f2: if f1+f2 == X you have found your solution else if f1+f2 > X decrease f2 to point to the element to its left else increase f1 to point to the element to its right

This step will take O(n) making the overall cost O(nlogn)

This solution is also referred to as the finger pointing solution. Can be used in any sorted collection where you can traverse in both the direction for eg in trees.

Answer 2

You probably meant if (A[left]+A[right]=X). Otherwise you would be comparing the same two elements over and over.

Even with this change your algorithm does not solve the problem. If e.g. $A[1]+A[N-2]=X$, it will never detect this.

Regarding complexity, your algorithm satisfies the recurrence $$T(N) = 2\cdot T\left(\frac N2\right) + 1.$$ Using the Master theorem, we find that the solution to this recurrence is in $\Theta(n) \subset \cal O(n \log n)$.

Answer 3

You can also use Balanced Binary Trees(BBT) for this. When you see the first $i$ elements of input, put them in BBT. Let the tree be called $T$. When you get $(i+1)$th element with value $y$, search $T$ for the element $X-y$. If present, report that there exist two elements with the given property. If not, put the $(i+1)$th element in tree and continue the process. If you don't find a pair that satisfies the given property even after inserting all $n$ elements, we can say that there is no such pair in the array with the given property.

Answer 4

Hint: Sort the array.

(This is always a good idea when you're aiming at $O(n\log n)$.)

Answer 5

Call the array A. A linear time algorithm exists if $\max A = \mathcal O(n)$.

insert the elements of A into a set S.
for every element a in A:
    if S contains x - a:
        return the pair (a, x - a)

This assumes that the set data structure's 'insert' and 'contains' run in constant time. One such data structure is the bit array.

Different data structures yield different running times. If S is a red-black tree, both the first line and the for loop take $\mathcal O(n \log n)$ and you get your bound.

Answer 6

All elements are assuming positive. If negative numbers exist, we can convert them to positives by adding the smallest number.

Solution One: Do an in-place merge sort on the array A. Loop through each item A[i], use a binary search to check if K-A[i] is in the array. If found, return the pair (A[i], K-A[i]); else, return null;

Time complexity is $O(n \log n )$; Space complexity $O(1)$.

Solution Two: Allocate an array m of size K. Find the first element in the array A[s] that is less than K, and set m[A[s]]=1. Loop through each remaining item A[i], check to see if m[K-A[i]] == 1. If m[K-A[i]] == 1, return the pair (A[i], K-A[i]); else return null in the end.

Time Complexity: $O(n)$ Space Complexity: $O(K)$

Here is the implementation details:

http://stones333.blogspot.com/2014/03/given-number-k-and-array-of-positive.html

Answer 7

Easiest solution:

• Put all elements in a hash map -> O(n) to O(n^2) depending on has function
• Iterate through list doing a lookup for (Sum - A[i]) -> O(n) with O(1) lookups
• If Sum is 2x A[i], check for second instance value in the map

Solution in O(n) to O(n^2) depending on has function