Two Pointers

Keep two indices moving over one list and let their relationship replace a nested loop. Touch each position a constant number of times and an O(n^2) scan becomes O(n), O(1) space. Two shapes: opposite ends (converge) and same direction (read/write).

Opposite ends (converging)

• Start left = 0, right = len - 1; loop while left < right; move one pointer inward each step.
• Two-sum on sorted: look at nums[left] + nums[right]. Equal -> found. Sum < target -> left += 1 (raise low end). Sum > target -> right -= 1 (lower high end).
• Safe to discard because sorted order makes each move change the sum in a known direction: the small value can’t reach the target with any smaller partner.
• Palindrome: compare s[left] vs s[right]; mismatch -> not a palindrome; else step both inward. Uses symmetry, no sorting needed.

two-sum, target 9:  [1, 3, 5, 8, 11]
 L                      R   sum 12 > 9 -> R--
 L                  R       sum 9  = 9 -> found (0, 3)

Same direction (read / write)

• Both start at front. read scans every item; write marks where the next kept item goes. Rebuilds the list in place, O(1) space.
• Remove duplicates (sorted): write = 0; for each read, if nums[read] != nums[write] then write += 1; nums[write] = nums[read]. Return write + 1 (a length is one past the last index).
• Move zeroes: for each read, if non-zero write it to nums[write] and write += 1; then fill nums[write:] with 0.
• The tail past the returned length is stale leftovers, not cleared — only nums[:length] is meaningful.

Precondition

• Needs a monotonic structure: as a pointer moves, the quantity you track changes one consistent direction.
• Usually sorted (two-sum, dedup) or symmetric (palindrome). Unsorted + order-dependent -> wrong answers silently; sort first (O(n log n)) or use a hash set.

Pitfalls

• Two-sum loop is left < right, not <= (never pair a value with itself).
• Every branch must move a pointer, or the loop never ends.
• write is an index; return write + 1 for a length — off-by-one drops or dupes the last item.
• Don’t run two-sum / dedup on unsorted data.

Summary table