The Two pointer Algorithm !!

A very easy but really effective algorithm..

I will try to describe this method on example of a problem.
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.

i and j our pointers, at first step i points to the first element of a, and j points to the last element of b.

i = 0; j = b.size() – 1;

move first pointer one by one through the array a, and decrease position of the second pointer if needed.
Here we are checking if a[i] +b[j] = X. If so, then write the answer. When this is not true, then if a[i] + b[j] > X, then decrease j (if j > 0), because what we need must be at a position less than current position of j or more than current position of i.

Now Take the example of this problem.
Consider problem 190D – Non-Secret Cypher. The stupid solution goes over all subarrays and checks whether it’s good or not. Now we notice that if subarray is ‘good’, then all its superarrays is ‘good’ too. Let’s go over all left borders x (1 ≤ x ≤ N) and for each of them find rx. rx is a minimal number such that subarray x… rx is good. Obviously, all subarrays which starts at x and ends after rx is good.

If you notice that r1 ≤ r2 ≤ … ≤ rN, you can use ‘two pointers’ method. The first pointer is x and the second one is rx. When you move the first one right, the second one can only move right too. No matter how many operations you perform in one step, algo’s running time is O(n), because each of pointers makes  ≤ N steps.

Now, try this problem by your own:-

Q> Given n numbers, find pairs with difference x.

Hint: First sort then apply the algo you have just learnt.

 
If you still can’t understand, then comment below..

2 thoughts on “The Two pointer Algorithm !!

  1. How does this method help achieving the better time or space complexity? What I mean is the algorithm implementation is not facilitating the <O(n^2) complexity.

    • You use at most 2 pointers. Each of them takes at most O(n) time. So, total time is O(n + n) = O(n).
      So this is facilitating the O(n^2) complexity.
      Space complexity is not reduced though.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s