The Two Pointers method is an algorithm used in computer programming to solve problems related to arrays and linked lists. This technique involves using two pointers pointing to different elements of an array or linked list and moving them towards each other to accomplish a specific task. In this blog post, we will take a closer look at this technique, understand its working, and learn how to implement it in C++.

Working of Two Pointers Method

The Two Pointers technique works by having two pointers start from opposite ends of an array or linked list and move towards each other. The idea behind this is that, when two pointers are moving towards each other, they eventually meet at a certain point, or they cross each other, depending on the problem statement. By having two pointers move towards each other, we can achieve several goals such as finding the middle element of an array, searching for a specific element, checking for a specific condition, and many more.

Examples of Two Pointers Method

1. Finding the Middle Element of an Array

Suppose we have an array of integers and we want to find the middle element of that array. In this case, we can use two pointers, one starting from the first element and the other starting from the last element, and move them towards each other until they meet in the middle.

#include <iostream>
using namespace std;

int main()
{
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    int first = 0, last = n - 1;

    while (first < last)
    {
        int mid = first + (last - first) / 2;
        if (arr[mid] < arr[last])
        {
            last = mid;
        }
        else
        {
            first = mid + 1;
        }
    }

    cout << arr[first] << endl;

    return 0;
}

Output:

3

1. Finding a Specific Element in an Array

Suppose we have an array of integers and we want to find whether a specific element is present in the array or not. In this case, we can use two pointers, one starting from the first element and the other starting from the last element, and move them towards each other until either they meet or the specific element is found.

#include <iostream>
using namespace std;

int main()
{
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 3;

    int first = 0, last = n - 1;

    while (first <= last)
    {
        int mid = first + (last - first) / 2;
        if (arr[mid] == x)
        {
            cout << "Element found at index " << mid << endl;
            return 0;
        }
        else if (arr[mid] < x)
        {
            first = mid + 1;
        }
        else
        {
            last = mid - 1;
        }
    }

    cout << "Element not found" << endl;

    return 0;
}

Output:

Element found at index 2