What is Two Pointers?

Two Pointers is a straightforward and flexible algorithmic technique used to solve problems efficiently, especially on arrays and strings. The basic idea is to use two pointers (or indices) to scan the data from different directions or at varying speeds.

Key Characteristics:

Usually works on sorted arrays or problems involving sequences.
Helps reduce nested loops, making algorithms faster.
Common in problems related to searching, comparing, or partitioning data.
Time complexity: typically \(O(n)\) or \(O(n \log n)\) depending on the problem.

How to Apply Two Pointers

Steps:

Decide the Purpose of Each Pointer:
- Will they move toward each other? At different speeds? Or scan simultaneously?
Initialize the Pointers:
- Start pointers at the beginning and end of the array, or both at the start.
Iterate Until a Condition is Met:
- Move the pointers based on the problem requirements.
- Adjust their movement when conditions are satisfied.
Exit Condition:
- Typically when the pointers cross or reach the end of the array.

Pseudocode

Basic Two Pointers Template:

# Example: Check if an array has two numbers that sum to a target

def two_pointers_example(array, target):
    left = 0  # Start of the array
    right = len(array) - 1  # End of the array

    while left < right:
        current_sum = array[left] + array[right]

        if current_sum == target:
            return (left, right)  # Found the pair
        elif current_sum < target:
            left += 1  # Move left pointer to increase the sum
        else:
            right -= 1  # Move right pointer to decrease the sum

    return -1  # No pair found

Common Patterns

Here are some popular problems solved using the Two Pointers technique:

1. Finding a Pair with a Given Sum

Problem: Find two numbers in a sorted array that add up to a target value.
Strategy: Use one pointer at the start and another at the end, adjust based on the sum.

2. Remove Duplicates from Sorted Array

Problem: Remove duplicates in-place in a sorted array and return the new length.
Strategy: Use one pointer to scan the array and another to track unique elements.

3. Reversing a String or Array

Problem: Reverse the characters in a string or elements in an array.
Strategy: Use two pointers, one at each end, and swap the elements.

4. Checking for Palindrome

Problem: Check if a string is a palindrome.
Strategy: Use two pointers, one at the start and one at the end, comparing characters.

5. Merging Two Sorted Arrays

Problem: Merge two sorted arrays into one sorted array.
Strategy: Use one pointer for each array and compare elements to decide which to add to the result.