3
$\begingroup$

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

$\endgroup$
2
  • 3
    $\begingroup$ The complexity is actually $O(n)$; that said, the "solution" doesn't work, so it's probably not what you're going for. Try your algorithm on [1, 4, 5, 7] to see if two elements sum to 9. Your algorithm will try 1+7, then 1+4, then 5+7 (ignoring the bugs that prevent it from even doing that). Hint: you can sort the entire array in $O(n\log n)$, at which point solving this problem is easy. $\endgroup$
    – Patrick87
    Feb 20, 2014 at 20:58
  • $\begingroup$ Another student in a course that uses Manber's book? $\endgroup$
    – Raphael
    Feb 25, 2014 at 20:22

7 Answers 7

9
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Hint: Sort the array.

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

$\endgroup$
2
  • $\begingroup$ By the way, this is indeed one way to get $O(n\log n)$. (Though that doesn't answer the question.) $\endgroup$ Feb 21, 2014 at 3:29
  • $\begingroup$ If an algorithm needs to work for sorted arrays as well, and is required to run in O (n log n), then you can always sort the array first. $\endgroup$
    – gnasher729
    May 20, 2018 at 8:52
1
$\begingroup$

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.

$\endgroup$
0
-2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Solution 2 doesn't seem to work. Presumably, you're assuming the array m is initialized to all-zero? But what does "return null in the end" mean? It seems that you only set one entry of m to 1 so the test m[K-A[i]]==1 can almost never return true. Is there some sort of loop that's missing? $\endgroup$ Mar 15, 2014 at 1:56
  • $\begingroup$ Additionally the time complexity of solution 2 is $\Theta(n+K)$. This is possibly much slower than ${\cal O}(n)$, since $K$ is independent of $n$. $\endgroup$
    – FrankW
    Mar 15, 2014 at 9:31
  • $\begingroup$ Here, I am assuming that all elements are positive. $\endgroup$
    – stones333
    Mar 16, 2014 at 1:34
-3
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ Why do you think that putting all elements in a hash map is $O(n \lg n)$ time? I think the most defensible answers are $O(n)$ time (expected time, using a sufficiently good hash function, like a 2-universal hash) or $O(n^2)$ time (worst-case running time). $\endgroup$
    – D.W.
    Feb 20, 2014 at 23:35
  • $\begingroup$ To be honest, it's been a while since I looked into hash maps, and working on memory of it being O(nlogn) on average when you accounted for collision handling etc on typical implementations $\endgroup$ Feb 20, 2014 at 23:45
  • $\begingroup$ OK, so let me rephrase. What I'm hinting at is that I think your memory isn't quite right. $\endgroup$
    – D.W.
    Feb 20, 2014 at 23:46

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.