Given a sorted array and a parameter k, find the count of sum of two numbers greater than or equal to k in linear time

Question

I am trying to find all pairs in an array with sum equal to k. My current solution takes O(n*log(n)) time (code snippet below).Can anybody help me in finding a better solution, O(n) or O(lgn) may be (if it exists)

 map<int,int> mymap;
 map<int,int>::iterator it;
 cin>>n>>k;
 for( int i = 0 ; i < n ; i++ ){
 cin>>a;
 
 if( mymap.find(a) != mymap.end() )
 mymap[a]++;
 else 
 mymap[a] = 1;
 
 }
 for( it = mymap.begin() ; it != mymap.end() ; it++ ){
 
 int val = it->first;
 
 if( mymap.find(k-val) != mymap.end() ){
 
 cnt += min( it->second, mymap.find(k-val)->second );
 it->second = 0;
 
 }
 
 }
 cout<<cnt;

• Karup: This might help.
• Ely: Before tackling, you risk to confuse the n of the complexity O(f(n)) and the n parameter given. You might consider renaming the parameter. Also I think the complexity is depending on the parameter, let's name it maybe k.
• Jarod42: As the array is sorted, when you add first and last and that the result is too big, which iterator to move, and which to move if it is lower ?
• SaCh: @PuRaK - That is not what I want. I need pairs whose sum >= k (not just sum = k)
• Ami Tavory: "I tried to find all pairs in the array with sum equal to n" That both contradicts the title, as well as being possible in (expected) linear time.

Answer 1

Another aproach which will take O(log n) in the best case and O(nlog n) in the worst one for positive numbers can be done in this way:

1. Find element in array that is equal to k/2 or if it doesn’t exist than finds the minimum greater then k/2. All combinations with this element and all greater elements will be interested for us because p + s>= k when p>= k/2 and s>=k/2. Array is sorted, so binary search with some modifications can be used. This step will take O(log n) time.
2. All elements which are less then k/2 + elements greater or equal to "mirror elements" (according to median k/2) will also be interested for us because p + s>= k when p=k/2-t and s>= k/2+t. Here we need to loop through elements less then k/2 and find their mirror elements (binary search). The loop should be stopped if mirror element is greater then the last array.

For instance we have array {1,3,5,8,11} and k = 10, so on the first step we will have k/2 = 5 and pairs {5,7}, {8,11}, {8, 11}. The count of these pairs will be calculated by formula l * (l - 1)/2 where l = count of elements>= k/2. In our case l = 3, so count = 3*2/2=3.

On the second step for 3 number a mirror element will be 7 (5-2=3 and 5+2=7), so pairs {3, 8} and {3, 11} will be interested. For 1 number mirror will be 9 (5-4=1 and 5+4=9), so {1, 11} is what we look for.

So, if k/2 < first array element this algorithm will be O(log n).

For negative the algorithm will be a little bit more complex but can be solved also with the same complexity.

Answer 2

There exists a rather simple O(n) approach using the so-called "two pointers" or "two iterators" approach. The key idea is to have two iterators (not necessarily C++ iterators, indices would do too) running on the same array so that if first iterator points to value x, then the second iterator points to the maximal element in the array that is less then k-x.

We will be increasing the first iterator, and while doing this we'll also change the second iterator to maintain this property. Note that as the first pointer increases, the corresponding position of the second pointer will only decrease, so on every iteration we can start from the position where we stopped at the previous iteration; we will never need to increase the second pointer. This is how we achieve O(n) time.

Code is like this (did not test this, but the idea should be clear)

vector<int> a; // the given array
int r = a.size() - 1; 
for (int l=0; l<a.size(); l++) {
 while ((r >= 0) && (a[r] >= k - a[l]))
 r--;
 // now r is the maximal position in a so that a[r] < k - a[l]
 // so all elements right to r form a needed pair with a[l]
 ans += a.size() - r - 1; // this is how many pairs we have starting at l
}

Another approach which might be simpler to code, but a bit slower, is O(n log n) using binary search. For each element a[l] of the array, you can find the maximal position r so that a[r]<k-a[l] using binary search (this is the same r as in the first algorithm).

• glear14195: The question asks that the sum of two numbers of the array be greater than k, not the sum of an array element and k. I think the condition should be (a[r]+a[l]<k).
• Petr: @glear14195, oh yes, my bad. Will fix the answer.
• Petr: @glear14195, if you mean the while condition, then I think mine is correct. r goes from right to left, so it should decrease as long as a[l]+a[r]>=k, which is what is written in my code.
• glear14195: Understood. You might wanna add a missing parentheses in the while condition though:)
• Petr: @glear14195, no, and that's the whole point! The array is sorted, and therefore while increasing l the corresponding r will only decrease. If I reinitialize it every time, it will be O(N^2), but using the fact that r only decreases, we turn it to O(N).

Answer 3

@Drew Dormann - thanks for the remark.

Run through the array with two pointers. left and right.
Assuming left is the small side, start with left at location 0 and then right moves towards left until a[left]+a[right] >= k for the last time.
When this is achieved, then total_count += (a.size - right + 1).
You then move left one step forwards and right needs to (maybe) move towards it. Repeat this until they meet.

When this is done, and let us say they met at location x, then totla_count += choose(2, a.size - x).

• NathanOliver: If a[left]+a[right] < n then moving right closer to left will still give you a result less then n.
• shapiro yaacov: @NathanOliver - a[left]+a[right] is bigger then n. When left moves one step to the right, right might be able to move leftwards and still keep a[left]+a[right] >= n

Answer 4

1. Sort the array (n log n)
2. for (i = 1 to n)
   • Start at the root
   • if a[i] + curr_node>= k, go left and match = indexof(curr_nod)e
   • else, go right
   • If curr_node = leaf node, add all nodes after a[match] to the list of valid pairs with a[i]

Step 2 also takes O(n log n). The for loop runs n times. Within the loop, we perform a binary search for each node i.e. log n steps. Hence the overall complexity of the algorithm is O (n log n).

• SaCh: The array is already sorted. Do you want to tell me to build a tree?
• Akshar: You don't have to. (You can though). Wha you can do is have the inner loop run from count = 0 to log n and at every step you would do a i + 2^count or i - 2^count depending on what condition is satisfied.

Answer 5

This should do the work:

void count(int A[], int n) //n being the number of terms in array
{ int i, j, k, count = 0;
 cin>>k;
 for(i = 0; i<n; i++)
 for(j = 0; j<n; j++)
 if(A[i] + A[j] >= k)
 count++ ;
 cout<<"There are "<<count<<" such numbers" ;
} 

• AndyG: This is an n-squared approach; a brute-force method. It can be done more efficiently.
• rachitmanit: She mentioned already she need a better method than Brute force.