Two Pointers

How it works

Two pointers replace a pair of nested loops with two indices that only ever move forward (or inward). The trick is a rule that tells you, after one comparison, which pointer can safely advance without skipping a possible answer.

With a sorted array and pointers at both ends, the rule comes from order: if the sum is too small, the left element can never be part of a solution with anything to the right, so it is discarded. Each step rules out a whole row of the brute-force grid, which is why the scan is linear.

The second shape is reader and writer: a fast pointer reads every element while a slow pointer marks where the next kept element goes. This is how you remove, compact or partition in place with O(1) memory.

Spot it when the input is sorted, when you compare from both ends (palindromes, containers), or when the problem says 'in place'. If the input is unsorted but order does not matter, sorting first is often the move that unlocks it.

How to attack it

1. 1Check whether the array is sorted, or whether sorting it loses nothing the answer needs.
2. 2Pick the shape: opposite ends moving inward, or slow writer and fast reader.
3. 3State the movement rule and why it never skips a valid answer.
4. 4Define the loop condition precisely (left < right versus left <= right).
5. 5Handle duplicates explicitly if the answer must be unique.

Template

A skeleton to adapt, not a solution to paste. Write it from memory a few times.

def pair_with_sum(nums, target):
    # nums must be sorted. Pointers start at both ends and move inward.
    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   # need a bigger sum: discard the smallest
        else:
            right -= 1  # need a smaller sum: discard the largest
    return []


def compact(nums, keep):
    # Slow pointer 'write' marks where the next kept element goes.
    write = 0
    for read in range(len(nums)):
        if keep(nums[read]):
            nums[write] = nums[read]
            write += 1
    return write  # new logical length

What it costs