Abinash's blog

What is Two Pointer tricks and how to implement it ?
By Abinash, 10 years ago, In English

I see it sometimes in editorial of CF round and in problems tag ?

But don't know what it is ? I searched and found something like that

Given two arrays (A and B) sorted in ascending order, and an integer x. we need to find i and j, such that a[i] + b[j] is equal to X.

But how to implement it and when it can be implemented for better result ?

Thanks in Advanced :)

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Two pointers means that in order to solve the problem, there is an invariant involving two indices. So for your problem above.

x = a[i]+b[j]. Since both arrays are sorted, we can use to pointers by using the first pointer to "watch" the first array a, and using the second pointer to navigate b.

observe that if b[j] < x-a[i] it means we should move forward on the second array.

if b[j] > x-a[i] then for all g > j we can't get the answer so i+=1;

Notice how both indices are moving in accord, they depend on each other.

Hope this helps.

→ Reply
»
10 years ago, # |
  Vote: I like it +7 Vote: I do not like it

the code, that solves this problem, looks like this:

//n - the length of the array A, m - the length of the array B
int j=m-1;
for (int i=0; i<n; ++i)
{
    while ((j>0) && (A[i]+B[j]>x))
    {
        j--;
    }
    if (A[i]+B[j]==x)
    {
        cout<<i<<" "<<j<<endl;
        return 0;
    }
}
cout<<"Not found!"<<endl;

I din't run the code anywhere, so it may contain some bugs.

The idea is as following. Consider the pair of indexes i1, i2, such as i2>i1. The following assumption is correct: if (A[i1]+B[j1] == x) and (A[i2]+B[j2] == x) then j2<=j1.

So in our code for each i we find the first index j, such as A[i]+B[j]<=x. If (A[i]+B[j]==x), then we find our pair. Otherwise, we continue looking. The total complexity is O(n+m), because i always increases and j always decreases

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I prefer using only one loop. I think its more beautiful.

for(int i = 0, j = m - 1; i < n && j >= 0;) {
    if(a[i] + b[j] > x) {
        j--;
    } else if(a[i] + b[j] < x) {
        i++;
    } else {
        printf("%d + %d = %d\n", a[i], b[j], x);
        i++; j--;
    }
}

The idea is as same as the other people's.

→ Reply
»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Two years later, I am looking for some stuffs on two pointer to send to a friends and I see my name on a comment :)

→ Reply