I tried to find all pairs in the array with sum equal to k, the solution to that takes O(n*log(n)) time. Here is the code snippet -

```
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;
```

I find it hard to find all pairs with sum greater than or equal to k. All I could think of is a O(n^2) solution to it. O(n^2) could be a brute force approach of finding all the pairs by iterating through the array. Can anybody help me in finding a better solution, O(n) or O(nlgn) may be (if it exists)

# Best How To :

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