Two Pointers Pattern

Two Pointers

Problem Scenario / Typical Use Case

Consider you are working with a sorted array of temperatures recorded over a month, and you want to find all pairs of days where the combined temperature equals a specific threshold.

Checking every possible pair would be inefficient for long datasets. The Two Pointers pattern provides a structured way to traverse the array linearly, leveraging the sorted order to find solutions efficiently.

Basic Idea

The Two Pointers pattern uses two references (pointers) moving through a data structure to explore relationships between elements:

• One pointer starts at the beginning, the other at the end.
• Both pointers move toward each other or in the same direction depending on the problem’s logic.

Typical operations include:

• Finding sums or differences.
• Checking for palindromes in strings.
• Compressing sequences or removing duplicates.

Advantages

• Efficiency: Reduces brute-force $O(n^2)$ approaches to $O(n)$.
• Clarity: Easy to visualize and reason about, especially on ordered datasets.
• Versatility: Combines well with Sliding Window or Prefix Sum.

Limitations / Considerations

• Works best on linear or sorted datasets.
• Less effective if elements don’t have a clear relational logic.
• Careful boundary management is essential to avoid off-by-one errors or infinite loops.
• Requires random access or indexable data structures (e.g., arrays, strings).

Practical Examples / Thought Triggers

1. Temperature Thresholds in a Sorted Array: Move pointers inward depending on whether the current sum is less or greater than the target.
2. Palindrome Detection in Strings: Compare characters from both ends, moving inward.
3. Removing Duplicates in a Sorted List: Skip duplicates with one pointer while building the result with another.

Thought Triggers:

• Should the data be sorted first? Sometimes sorting (cost $O(n log n)$) makes this pattern applicable.
• Can this combine with a sliding window for contiguous subarrays?
• Would extra space with a hashmap simplify the solution in some cases?

Implementation Example

Here’s a Python example for finding pairs in a sorted array that sum to a target:

def two_pointer_pairs(arr, target):
    left = 0
    right = len(arr) - 1
    pairs = []

    while left < right:
        current_sum = arr[left] + arr[right]
        if current_sum == target:
            pairs.append((arr[left], arr[right]))
            left += 1
            right -= 1
        elif current_sum < target:
            left += 1
        else:
            right -= 1

    return pairs

# Example usage
temperatures = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target_sum = 10
print(two_pointer_pairs(temperatures, target_sum))
# Output: [(1, 9), (2, 8), (3, 7), (4, 6)]

This code illustrates the core concept: two pointers moving towards each other, adjusting based on the sum relative to the target.

Related Articles

• Sliding Window: Useful when searching for contiguous subarrays or substrings satisfying conditions.
• Binary Search: Two pointers can define ranges for a subsequent binary search.
• Prefix Sum: Combining with two pointers allows efficient sum calculations over ranges.