In this article, we have explained the Two Pointer Technique/ algorithm in array which is used to solve a vast range of problems efficiently. Problems include Reversing an array and Find if a pair with given sum exists in a sorted array.

Table of contents:

1. Introduction to Two Pointer Technique
2. Example Problem 1: Reverse an array
3. Example Problem 2: Find if a pair with given sum exists in a sorted array

Let us get started with Two Pointer Technique.

Introduction to Two Pointer Technique

Two pointer Technique is a widely used technique for solving various problems based on arrays. This is particularly useful for sorted arrays and can help solve a wide variety of problems. As the name suggests, we use 2 'pointers' that point to certain elements in the array. The pointers are manipulated according to some conditions (depends on the problem) until they meet (might vary).

Two pointer approach essentially uses 2 pointers. The pointers can be used in different ways according to the use case. For example:

• One pointer can be a slow runner while the other one can be the fast runner. This technique is typically widely for problems based on linked lists.

• One pointer points to the first element while other points to the last element of the array. Used for problems on sorted arrays.

Let's understand this technique better with an example problem. Please note that the two pointer approach has several applications and is not limited to this specific problem.

Example Problem 1: Reverse an array

Given an array, we need to reverse it.
arr = [2,5,3,7,4]
Reversed arr = [4,7,3,5,2]

A commonly used method to solve this problem uses the 2 pointer approach. One pointer points to the first element while the second on points to the last element. The elements pointed to by the pointers are swapped and the one pointing to the first elemnt is incremented whereas the one pointing to the last element is decremented (Condition for manipulation). This continues until the pointers meet (Condition for stopping).

Code

Following is the implementation using Two Pointer Technique in Java:

public static void reverseArray(int arr[], int n)
{
    int  i = 0, j = n-1;
    while(i < j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        i++;
        j--;
    }
}

Following is the implementation using Two Pointer Technique in C++:

void reverseArray(int arr[], int n)
{
    int  i = 0, j = n-1;
    while(i < j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        i++;
        j--;
    }
}

Time and Space Complexity

Time complexity is O(N) because the array is traversed just once.
Space complexity is O(1). No auxiliary space is used.

Example Problem 2: Find if a pair with given sum exists in a sorted array

Given a sorted array and a number K, we need to find if there exists a pair of elements such that their sum is equal to the given number K. There are multiple ways of solving this problem (some are more efficient than others).

We will be discussing a solution that uses the 2 pointer approach as the pivotal algorithm.

Note that the array is sorted.

Example:
arr = [1,4,5,7,10], K = 12

The pair (5,7) yields a sum of 12 which is equal to 12.
Dry run:

• i = 0, j = 4 => arr[i] + arr[j] = 11, which is less than 12, hence i++.
• i = 1, j = 4 => 4 + 10 = 14 and 14 > K, decrement j, j--.
• i = 1, j = 3 => 4 + 7 = 11 and 11 < K, increment i, i++.
• i = 2, j = 3 => 5 + 7 = 12, which equals the given sum K, return true.

Algorithm

1. We use 2 pointers, one pointing to the first element(Let's call it i) and the other pointing to the last one(Let's call this one j).
2. While the 2 pointers don't cross each other, we do this:
   2.1 We calculate the sum of both these elements.
   2.2 Compare the sum with the given value K.
   2.2.1 If sum == K, return true.
   2.2.2 If sum < K, increment i.
   2.2.3 If sum > K, decrement j.
3. Return false.

This logic invoving the 2 pointer approach works in this case because, the arrat is sorted. This ensures that we don't miss out on any potential pair.
When sum < K, we increment i, and it starts pointing to a number greater than the current element. This increases the sum and might bring it closer (or even exceed) K. However, any number smaller than the current element will result in a smaller sum which will definitely be smaller than K. Hence, we increment i and not decrese it.

Similarly, it makes sense to decrement j when sum > K because decrementing j will make the sum smaller than before as the new element being used is smaller than the current one.

Code

Following is the implementation using Two Pointer Technique in Java:

    public static boolean pairExists(int arr[], int K)
    {
        int  i = 0, j = arr.length - 1;
        while(i < j)
        {
            if(arr[i] + arr[j] == K)
                return true;
            
            else if(arr[i] + arr[j] < K)
                i++;
            else
                j--;
        }
        return false;
    }

Following is the implementation using Two Pointer Technique in C++:

bool pairExists(int arr[], int n, int K)
{
    int  i = 0, j = n-1;
    while(i < j)
    {
        if(arr[i] + arr[j] == K)
            return true;
        else if(arr[i] + arr[j] < K)
            i++;
        else
            j--;
    }
    return false;
}

Time and Space Complexity

Using the 2 pointer approach helps reduce the time complexity to O(N). We are able to find out if a pair with the given sum exists in the array in just one traversal of the array.

This approach does not require any auxiliary space, hence, space complexity is O(1).

With this article at OpenGenus, you must have a complete idea of Two Pointer technique in Array and how to use it to solve problems.