Two-Pointer Techniques for Sorted Arrays and Strings

Hello! In the previous lesson, you found pairs in an unsorted list by storing earlier values in a dictionary or set. When an array is sorted, its order gives you another option: move two indices according to what the values tell you. Strings offer a related opportunity—you can compare characters from opposite ends without building a copy.

This lesson develops two common two-pointer patterns: pointers moving inward to find a pair or check a string, and pointers moving forward to compact a sorted array. The goal is not just to remember where the pointers start, but to know why each move is safe.

Find a target sum in a sorted array

Suppose nums = [1, 2, 3, 4, 6] and target = 6. Place left at the smallest value and right at the largest. Their sum is $1+6=7$, which is too large. Because the array is sorted, moving right left is the useful move: it can lower the sum. The next sum, $1+4=5$, is too small, so move left right. Now $2+4=6$.

Watch NeetCode’s TWO SUM II - Amazon Coding Interview Question - Leetcode 167 - Python for a visual walkthrough and implementation. That particular problem requests one-based indices; the code below uses Python’s usual zero-based indices instead.

Here is a version that returns zero-based indices, or None if no pair exists:

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

    while left < right:
        total = nums[left] + nums[right]

        if total == target:
            return [left, right]
        if total < target:
            left += 1
        else:
            right -= 1

    return None

Why can you discard an endpoint? If nums[left] + nums[right] is below the target, pairing nums[left] with any value between the pointers gives a sum no larger. Thus nums[left] cannot be in a valid pair among the remaining positions. Moving left is safe. Conversely, if the sum is above the target, pairing nums[right] with any remaining value gives a sum no smaller, so moving right is safe. This reasoning also works when values repeat.

Use left < right, not left <= right: a pair requires two distinct indices. Each iteration either returns or moves one pointer inward, so the algorithm takes $O(n)$ time and $O(1)$ auxiliary space.

The sorted-input requirement matters. On an unsorted array, a value to the right might be smaller, so these discard arguments fail; the dictionary approach from the previous lesson remains useful. Sorting first also changes positions, which matters if the answer must give original indices. Always check the input and output contract before choosing the pattern.

Compare a string from both ends

Two pointers do not require a sorted string. They also work when a question concerns matching positions at opposite ends. Consider a palindrome check that ignores punctuation and spaces and treats letters case-insensitively: "A man, a plan, a canal: Panama" should pass.

A straightforward approach could construct a cleaned string and compare it with its reverse. Instead, keep one index at each end of the original string. Skip characters that do not count; when both indices reach relevant characters, compare them. Every successful comparison settles an outer pair, leaving only the characters between the pointers to check.

Read NeetCode’s 125. Valid Palindrome - Solution & Explanation for this inward-moving pattern.

In Python, the logic can be expressed directly:

def is_valid_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 left >= right:
            break

        if s[left].lower() != s[right].lower():
            return False

        left += 1
        right -= 1

    return True

The boundary checks in the inner loops matter. A string containing only punctuation may leave no characters to compare, yet it must not produce an index error. An empty string likewise finishes without a mismatch. Here .isalnum() follows Python’s definition of letters and digits; if a problem explicitly specifies ASCII-only characters, its character test must match that narrower rule.

Each pointer moves only inward and visits at most $n$ positions in total. The time is $O(n)$, with $O(1)$ auxiliary space. Unlike the sorted-pair problem, you move both pointers after a successful comparison because both outer characters have been settled.

Move both pointers forward to remove duplicates

“Two pointers” can also mean two indices traveling in the same direction. Suppose a sorted list must be modified so that each distinct value appears once at its front. For [0, 0, 1, 1, 1, 2, 3, 3, 4], the desired front portion is [0, 1, 2, 3, 4].

Use read to inspect the original values and write to mark the next position in the unique prefix. Because the list is sorted, any new distinct value differs from the last value kept. You need not compare it with every earlier value.

The image calls the last kept position left. In this implementation, write points one position after the last kept value:

def compact_unique(nums):
    if not nums:
        return 0

    write = 1

    for read in range(1, len(nums)):
        if nums[read] != nums[write - 1]:
            nums[write] = nums[read]
            write += 1

    return write

The return value is the number of unique elements, not the last unique index. For the example, it returns 5, and nums[:5] is [0, 1, 2, 3, 4]. Positions beyond write may still contain old values; they are outside the valid result.

A useful rule to track is: before each read step, nums[:write] contains the distinct values encountered so far, in order. If the new value equals nums[write - 1], it is a duplicate. Otherwise, writing it at write extends that valid prefix. The scan takes $O(n)$ time and $O(1)$ auxiliary space because it changes the given list rather than allocating a second list. If modifying the input is forbidden, this exact solution does not satisfy the contract.

Key takeaways

Two pointers are valuable when order or position makes a pointer move defensible:

• In a sorted pair search, a sum that is too small rules out the left endpoint; a sum that is too large rules out the right endpoint.
• In a palindrome check, skipping irrelevant characters and matching outer characters reduces what remains to be checked.
• In sorted-array compaction, a scanning index discovers values while a writing index maintains the valid result prefix.

For each new problem, identify what the pointers represent, when they stop, and why advancing one cannot discard an answer. Next, you’ll use a related idea to maintain a fixed-size sliding window, updating its state as it moves across a sequence.