Introduction

Two pointers is really an easy and effective technique which is typically used for searching pairs(triplets, etc) in a sorted(or partially sorted) array.

Approach

1. According to specific condition decrement or increment start or end pointer to achieve result.

   Init start and end pointers. Depends on conditions it might be the first and last elements of the input array or it might point to first or last elements only.

Example

<aside> 📖 Given an array of sorted numbers and a target sum, find a pair in the array whose sum is equal to the given target.

</aside>

Given that the input array is sorted, an efficient way would be to start with one pointer in the beginning and another pointer at the end. At every step, we will see if the numbers pointed by the two pointers add up to the target sum. If they do not, we will do one of two things:

1. If the sum of the two numbers pointed by the two pointers is greater than the target sum, this means that we need a pair with a smaller sum. So, to try more pairs, we can decrement the end-pointer.
2. If the sum of the two numbers pointed by the two pointers is smaller than the target sum, this means that we need a pair with a larger sum. So, to try more pairs, we can increment the start-pointer.

Basic pattern

//two sum
int[] search(int[] arr, int targetSum) {
    if (arr.length == 0) return new int[]{-1, -1};
    int lo = 0, hi = arr.length - 1;
    while (lo < hi) {
        int sum = arr[lo] + arr[hi];
        if (sum == targetSum) {
            return new int[]{lo, hi};
        }
        if (arr[lo] + arr[hi] < targetSum) {
            lo++;
        } else {
            hi--;
        }
    }
    return new int[]{-1, -1};
}

List of questions

Untitled

Complexities

Two pointers in most of the cases allows to decrease $O(N^2)$ to $O(N)$ using one loop only.

For basic approach without additional input : $O(n)$ time and $O(1)$ space.

Time complexity might grow, depends of number of loops.

Links

Introduction