Two Pointers

Consider two pointers when sorted order lets you discard candidates, when two ordered streams must be combined, or when an array must be filtered or partitioned in place. Two indices alone do not guarantee a linear algorithm: explain why each move is safe and why neither pointer repeatedly backtracks.

1. Discard Candidates from the Ends

For a sorted array and target sum, start at left=0, right=n-1. If the pair sum is too small, even the largest remaining partner cannot rescue nums[left], so discard it. If too large, even the smallest remaining partner makes nums[right] too large, so discard that endpoint.

Use left < right when a pair must contain two distinct positions. Each step removes one position from consideration: $O(n)$ time, $O(1)$ extra space. Sorting an unsorted input first adds $O(n\log n)$ and may lose original indices; compare a hash-map solution when indices must be returned.

For Container With Most Water, move the shorter wall: with that wall fixed, moving the taller wall inward only reduces width and cannot raise the limiting height. Similar-looking pointer movements need their own justification; sorted order is not the argument here.

For palindromes that ignore punctuation, validate both bounds while skipping characters. An empty or all-punctuation input must terminate without an out-of-bounds read.

2. Recipe: Seeker and Writer

The reference chapter's named recipe separates where to read next from where the next retained value belongs. For deduplicating a sorted array:

def deduplicate(nums):
    writer = 0
    for seeker in range(len(nums)):
        if writer == 0 or nums[seeker] != nums[writer - 1]:
            nums[writer] = nums[seeker]
            writer += 1
    return writer

Before each read, nums[:writer] is the deduplicated result for the processed prefix, and writer <= seeker. Writing cannot overwrite unread input. Compare with the last retained value, since earlier positions may already have changed. The return value is the valid prefix length; the trailing elements are irrelevant. Time is $O(n)$, space $O(1)$, and retained order is preserved.

For Remove Element, change the keep condition to nums[seeker] != target. If output expands, reading and writing from the left may overwrite unread values: Merge Sorted Array instead fills spare capacity from the right, always writing the larger remaining item.

3. Merge, Intersect, or Partition

Two sorted streams: compare their current items and advance the one that can no longer affect the next result. A merge emits the smaller value and later drains the nonempty tail; an intersection emits equal values and advances both. Define whether duplicates are counted or collapsed. Total time is $O(n+m)$; output storage is separate.

For two lists of internally disjoint sorted intervals, the current intersection is [max(start1,start2), min(end1,end2)] if its start does not exceed its end. Advance the interval that ends first: it cannot overlap a later interval from the other list. If ends tie, both may advance. See Interval List Intersections.

Three-way partition: maintain < pivot in [0,low), == pivot in [low,scan), unknown values in [scan,high], and > pivot after high. A smaller value swaps to low and advances both low and scan; an equal value advances scan; a larger value swaps with high and only decrements high. Do not advance scan in the last case: the swapped-in value has not been inspected. This gives $O(n)$ time and $O(1)$ space, usually without stability.

To rotate or exchange adjacent unequal-length blocks A B into B A, reverse A, reverse B, then reverse the whole range. Internal order is restored by the final reversal. The total is $O(n)$ time and $O(1)$ space; the Prefix-Suffix Swap variation applies this identity.

4. Key Takeaways

• Sorted two-sum discards an endpoint only after ruling out all its remaining partners.
• A writer must not pass unread input; filter left to right, but merge into spare tail capacity right to left.
• After swapping an unknown value from the right side of a partition, inspect it before moving on.
• State whether endpoints are inclusive, positions must differ, and duplicates or original order matter.

Continue to Sliding Windows for contiguous ranges with maintained state, Linked Lists for fast/slow node pointers, and Sorting for merging and partitioning as larger algorithm steps.