Algorithm Techniques: Two Pointers

What is the two pointers technique?

A more flexible variation of the sliding window technique, the two pointers used in this technique can move independently or in tandem through data structures.

When is this technique useful?

This is a common pattern that can be used in a wide range of algorithms. Each pointer refers to an index and travels through the array/string/linked list in order to solve a problem. If the problem requires finding pairs, a specific subsequence, or checking for a palindrome, consider using the two pointer technique.

In the examples below, two pointers are used to accomplish a variety of tasks.

Common examples:

• Sorting Colors (with JS) This function uses two pointers to sort an array of integers in-place.

function sortColors(nums: number[]): void {
    // two pointers
    let left = 0, mid = 0;
    let right = nums.length - 1;

    while (mid <= right) {
        if (nums[mid] === 0) {
            [nums[left], nums[mid]] = [nums[mid], nums[left]];
            left++;
            mid++;
        } else if (nums[mid] === 2) {
            [nums[mid], nums[right]] = [nums[right], nums[mid]];
            right--;
        } else {
            mid++;
        }
    }
};

• Merging Arrays In this simple array merging algorithm, a two pointers travel down two separate sorted arrays, while a third one inserts the larger of the pair. This maintains the nondecreasing order while merging.

function merge(nums1: number[], m: number, nums2: number[], n: number): void {
    let mPointer = m - 1;
    let nPointer = n - 1;
    let insertionInd = m + n - 1;

    while (nPointer >= 0) {
        if (nums1[mPointer] > nums2[nPointer]) {
            nums1[insertionInd] = nums1[mPointer];
            mPointer--;
        } else {
            nums1[insertionInd] = nums2[nPointer];
            nPointer--;
        }
        insertionInd--;
    }
};

• Finding Palindromic Substrings Finally, two pointers are used in this example to identify palindromes. After successfully identifying one, the pointers move to the left and right sides to search for an even longer palindrome.

function countSubstrings(s: string): number {
    let count = 0;

    for (let i = 0; i < s.length; i++) {
        expand(i, i); // check for odd-length palindromes
        expand(i, i + 1); // check for even-length palindromes
    }
    return count;

    function expand(left, right) {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            count++;
            left--;
            right++;
        }
    }
};