The two-pointers approach for array and string problems

Array and string problems are often used in technical pre-screens or during coding interviews. This article describes how to use the two-pointers approach to solve them.

The two-pointers approach uses two integer variables, which each represent an index of an iterable, and move along it. These integers are most often named either i and j, or left and right.

One common method to implement two-pointers is to start one pointer at the first index 0, and the other pointer at the last index iterable.length – 1. In a while loop, move the pointers towards each other until they are equal to each other. It is possible to move either only one of the pointers or both. It depends on the presented problem, which pointers should move.

One advantage of this method is that there can never be more than O(n) iterations for the while loop. If the logic inside each iteration can be kept at O(1), the algorithm will have a linear runtime.

Example 1: Check whether a given string is a palindrome.

A string is a palindrome if it reads the same forwards as backwards, e.g. "Anna". We can use the two-pointers approach to check if all corresponding i^th and n - i - 1^th characters are the same.

def check_if_palindrome(s):
    '''Use two pointers to check 
       if an input iterable is a palindrome'''
    left = 0
    right = len(s) - 1

    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1

    return True


print(check_if_palindrome('racecar'))  # True
print(check_if_palindrome('packers'))  # False

Example 2: Given a sorted array of unique integers and a target integer, return true if there exists a pair of numbers that sum to target, false otherwise.

Because the array is sorted, we don’t have to iterate over all pairs integers and can therefore improve the time complexity from O(n^2) to O(n). The first step is to add the first and the last number of the array. If the sum is greater than the target, we need to move the right pointer to make the sum smaller. Otherwise, we move the left pointer to make the sum bigger. We continue until we have found the combination of numbers that add up to the target sum.

def check_for_target(nums, target):
    left = 0
    right = len(nums) - 1

    while left < right:
        curr = nums[left] + nums[right]
        if curr == target:
            return True
        if curr > target:
            right -= 1
        else:
            left += 1

    return False


print(check_for_target(
[1, 3, 4, 7, 11, 12, 16, 20], target=18)
)  # True

Example 3: Given two sorted integer arrays, return an array that combines both of them and is also sorted.

For this task, we have one pointer for each array that start at the first index of the respective array. At each iteration of a while loop, we compare the two values. The lower value gets added to the newly created result array, and the respective pointer moves. Finally, we add the remaining values from both arrays to the result array.

def combine(arr1, arr2):
    result= []
    i = j = 0
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            result.append(arr1[i])
            i += 1
        else:
            result.append(arr2[j])
            j += 1

    while i < len(arr1):
        result.append(arr1[i])
        i += 1

    while j < len(arr2):
        result.append(arr2[j])
        j += 1

    return result


print(combine([2, 4, 8, 12], [3, 7, 21, 35, 52]))
# [2, 3, 4, 7, 8, 12, 21, 35, 52]

The above examples described some common patterns using two pointers, but there are still different ways to implement them. Hopefully, this article helps as a starting point.