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
    $\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 '14 at 20:58
  • $\begingroup$ Another student in a course that uses Manber's book? $\endgroup$ – Raphael Feb 25 '14 at 20:22
7
$\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$
  • $\begingroup$ By the way, this is indeed one way to get $O(n\log n)$. (Though that doesn't answer the question.) $\endgroup$ – Yuval Filmus Feb 21 '14 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 '18 at 8:52
0
$\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$
-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$
  • $\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$ – David Richerby Mar 15 '14 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 '14 at 9:31
  • $\begingroup$ Here, I am assuming that all elements are positive. $\endgroup$ – stones333 Mar 16 '14 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$
  • 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 '14 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$ – SeeMoreGain Feb 20 '14 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 '14 at 23:46

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.