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 **N**^{th} 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 N^{th} 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 **arguments**: **reference **to **head and N** and you need to** return N ^{th} **from the end.

**Expected Time Complexity:**O(N).

**Expected Auxiliary Space:**O(1).

**Constraints:**

1 <= T <= 200

1 <= L <= 10

^{3}

1 <= N <= 10

^{3}

**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 1:

**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,

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

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

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

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 ≤ 10^{5}

1 ≤ A[i] ≤ 10^{5}**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.

Testcases 1:

**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..!!!