The two pointers pattern is a versatile and efficient technique widely used in algorithmic problem-solving, especially when working with sequential data structures like arrays, strings, or linked lists. As the name suggests, this approach involves maintaining two pointers (or indices) that traverse the data structure in a coordinated manner—often starting from different positions or moving in opposite directions. By dynamically adjusting these pointers based on specific conditions, we can efficiently explore the data and solve problems with optimal time and space complexity.

Whenever you need to find two elements in a sequence that satisfy a certain condition, the two pointers pattern should be one of the first strategies you consider.

About the pattern

The two pointers technique is particularly useful when:

• You need to process or compare elements at different positions in a linear data structure.
• The problem involves searching for pairs or subarrays that meet certain criteria.
• You want to optimize for time and space, often reducing the need for nested loops.

The pointers can move in the same direction, in opposite directions, or even traverse two different data structures, depending on the problem.

Example: Checking for palindromes

A classic example is checking if a string is a palindrome (reads the same forwards and backwards). Here, one pointer starts at the beginning and the other at the end, moving towards each other while comparing characters.

def is_palindrome(s):
    left, right = 0, len(s) - 1

    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True

def main():
    test_cases = [
        "A man, a plan, a canal: Panama",
        "race a car",
        "1A@2!3 23!2@a1",
        "No 'x' in Nixon",
        "12321",
    ]
    for s in test_cases:
        print(f"\tstring: {s}")
        result = is_palindrome(s)
        print(f"\n\tResult: {result}")
        print("-" * 100)

if __name__ == "__main__":
    main()

Why is this efficient?
A naive approach might use nested loops, resulting in O(n²) time complexity. The two pointers method, however, only requires a single pass through the string—O(n) time.

More examples

Here are some classic problems that benefit from the two pointers pattern:

1. Reversing an array
   Reverse an array in place by swapping elements from both ends, moving towards the center.

2. Pair with given sum in a sorted array
   Given a sorted array and a target sum, use two pointers (one at the start, one at the end) to find a pair that adds up to the target.

Real-world problems

The two pointers pattern isn't just for coding interviews. It appears in real-world systems too. For example:

• Memory management:
  In memory allocation, two pointers can represent the start and end of a memory block. Allocation moves the start pointer forward; deallocation can move it backward, efficiently managing available memory.

Does your problem match this pattern?

Consider using the two pointers technique if:

• Linear data structure: Your input is a sequence (array, string, linked list).
• Process pairs: You need to process or compare elements at two different positions.
• Dynamic pointer movement: Both pointers can move independently based on certain conditions.