Two Pointer Algorithm

Two Pointer Algorithm

Today we are going to discuss a trending Algorithm which is used frequently for solving problems the Two Pointer Algorithm.

In this post, we will first understand the Two Pointer Algorithm and then we will solve 2-3 problems based on it. Also, I will give problems for practice so that you can understand this Algorithm more clearly. So let’s start[Greedy Algorithm].

Technical Definition

Two Pointer Technique uses two-pointer in one loop over the given data structure. It is commonly used for solving array, string, linked list coding problems.

The main purpose of this algorithm is to reduce the complexity of O(n^3) or O(n^2) based solution to Linear time solution.

Common patterns in the two pointer algorithm approach involve-

(i) Two pointers each starting from the beginning and the end until they both meet.
(ii) One pointer moves at a slow pace while the other pointer moves at a faster pace.
(iii) Pointer-I and Pointer-II from two sequences.

We will discuss Questions to discuss the following Patterns.[Merge Sort Algorithms][Bubble Sort Algorithm]

Nth node from end of linked list

Given a linked list consisting of L nodes and given a number N. The task is to find the Nth node from the end of the linked list.

Input:
The first line of input contains the number of testcase T. For each testcase, the first line of input contains the number of nodes in the linked list and the number N. The next line contains N nodes of the linked list.

Output:
For each testcase, output the data of node which is at Nth distance from the end or -1 in case node doesn’t exist.

User Task:
The task is to complete the function getNthFromLast() which takes two argumentsreference to head and N and you need to return Nth from the end.

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Constraints:
1 <= T <= 200
1 <= L <= 103
1 <= N <= 103

Example:
Input:
2
9 2
1 2 3 4 5 6 7 8 9
4 5
10 5 100 5

Output:
8
-1

Explanation:
Testcase 1:
 In the first example, there are 9 nodes in linked list and we need to find 2nd node from end. 2nd node from end is 8.  

Testcase 2: In the second example, there are 4 nodes in the linked list and we need to find 5th from the end. Since ‘n’ is more than the number of nodes in the linked list, the output is -1.

Analysis of Problem Statement

The problem seems simple and you might be thinking why the hell I am discussing this Question.

Yes, Problem Statement is simple and also the solution too but if I bring one extra constraint to this Question, then this problem becomes interesting.

And my motive to discuss any question is that you should learn something from it.

Naive Solution

I think the Problem statement is clear. You have to find the nth node of the linked list from the end.

The solution is simple, just count the number of nodes present in the linked list in the first traversal and then find the Nth node from the end in the second traversal.

Let’s see it’s code,

int getNthFromLast(Node *head, int n)
{
     Node *t = head,*t1 = head;  
     int k = 0;
     
     while(t != NULL)  
     {
         t=t->next;   
         k++;
     }
     if(k < n)  return -1;
     else
     {
         for(int i = 0; i < (k - n); i++)   
         {
             t1 = t1->next;
             
         }
         return (t1->data);
    }
}

I think above code is simple and time complexity is also O(n) but what if I tell you that you have to find the nth node from the end in just one traversal.

I mean that in the above code you need two traversal to find the result, but can you find the result in just one traversal.

It is highly recommended to think of a way to approach this problem in only one traversal.

Nth node from end in just One Traversal

The logic behind this solution is based on Two Pointer Approach. Let’s understand it more clearly.

Let’s take an example,

two pointer algorithm

And in the above we have to find 3rd node from end.

Now in the previous approach we were first traversing from 1st node to last node and then we were coming backward to find nth node from end or (k-n)th node from the front in the second traversal.

Do we need to go to the last node and come back again..??

To understand it clearly, let’s do a bit of Mathematics.

Let’s assume there are ‘k’ number of nodes with us. And we have to find nth node from the back.

two pointer algorithm

Now nth node from the back is actually (k-n)th node from the front.

two pointer algorithm

Now let us understand one thing, We can achieve this by another process too.

two pointer algorithm

In this algorithm, we will declare two-pointer both initialised to head initially. Now we will move Pointer 1 till Nth node. When Pointer 1 reaches the Nth node, at the same time we will move Pointer 2. We will move both the pointers simultaneously till Pointer 1 reaches the last position.

The distance travelled by both the pointer will be same after Pointer 1 crosses Nth node.

Now Total distance travelled by Pointer 1: K
Total distance travelled by Pointer 2 : (K – n)

Let us analyse how Pointer 2 travelled (K – n) distance from the front. How we are sure about it?

The reason behind is that when we started Pointer 2 to move, when Pointer 1 was at position N. So after that distance travelled by Pointer 1 is (K-n) which is same as distance travelled by Pointer 2 as well. But since Pointer 2 started it’s journey from starting point, that’s why total distance travelled by Pointer 2 is (K-n-0) which is (K – n) and the node present at this position is our resultant node.

Hope you understood the logic behind this Algorithm. This is one application of Two Pointer Approach.

Let’s see the code,

int getNthFromLast(Node *head, int n)
{
    Node *ptr1 = head, *ptr2 = head;
    for(int i=1; i <= n-1; i++){
        ptr1 = ptr1->next;
        if(ptr1 == NULL) return -1;
    }
    
    while(ptr1->next != NULL){
        ptr2 = ptr2->next;
        ptr1 = ptr1->next;
    }
    return ptr2->data;
}

In this way, we can find nth node from end in just one traversal. Now let’s move ahead to solve one more Question.

Problem : Key Pair[Two Pointer Algorithm]

Given an array A of N positive integers and another number X. Determine whether or not there exist two elements in A whose sum is exactly X.

Input:
The first line of input contains an integer T denoting the number of test cases. The first line of each test case is N and X, N is the size of array. The second line of each test case contains N integers representing array elements A[i].

Output:
Print “Yes” if there exist two elements in A whose sum is exactly X, else “No” (without quotes).

Constraints:
1 ≤ T ≤ 100
01 ≤ N ≤ 105
1 ≤ A[i] ≤ 105

Example:
Input:

2
6 16
1 4 45 6 10 8
5 10
1 2 4 3 6

Output:
Yes
Yes

Explanation:
Testcases 1:
 10 and 6 are numbers making a pair whose sum is equal to 16.

Naive Method

Naive Method is to run two nested loops and find that if two numbers add up to the specific target or not. This process takes O(n^2) time complexity.

bool twoSum(vector<int>& nums, int target) {
    for (int i = 0; i < nums.size(); i++) 
    {
        for (int j = i+1; j < nums.size(); j++) 
        {
            if (nums[i] + nums[j] == target) {
                return true;
            }
        }
    }
    return false;
}

Two Pointer Approach

We can reduce the complexity to O(n) by Two Pointer Approach. Let’s see it.

Since Array is sorted, we can use two Pointer here. We will keep one pointer at the first element and second pointer at the last element.

Since Array is sorted, if sum of both the element if greater than target sum, we will update out second pointer or else we will update our first pointer.

Let’s see it’s code.

bool twoSum(vector<int>& nums, int target) {

        int pointerOne = 0;
        int pointerTwo = nums.size() - 1;

        while (pointerOne < pointerTwo) 
        {
            int sum = nums[pointerOne] + nums[pointerTwo];

            if (sum == target) {
                return true;
            } 

            else if (sum < target) {
                pointerOne++;
            } 

            else {
                pointerTwo--;
            }
        }
        return false;
    }

We will discuss more Problems on Two pointer algorithm in our next Post. Hope you understood the basics of Two Pointer Approach.

That’s all folks..!!!

Tagged : /

Leave a Reply

Your email address will not be published. Required fields are marked *