Two pointers

Two pointers

A pointer here is just an index variable. The two-pointer pattern keeps two of them, usually lo at the start and hi at the end, and moves them toward each other based on what they see.

Take pair-sum on a sorted list: does any pair add to target?

• If nums[lo] + nums[hi] is too small, the only way to grow the sum is lo += 1 (everything left of hi paired with nums[lo] would be even smaller, so nums[lo] is dead, discard it).
• If it is too big, shrink with hi -= 1 for the mirror reason.
• Equal? Found it.

Every step permanently retires one element, so the whole scan is O(n) time, O(1) space. Compare that with lesson 1-1: the set solution was O(n) time but O(n) space. Sortedness bought us the memory back.

Same-direction pointers: reader and writer

Converging lo/hi pointers are half the pattern. The other half moves two pointers the same direction at different speeds, usually named read and write. The reason this variant exists: many problems demand you edit a list in place — O(1) extra space, no second list — and one index cannot both scan the input and mark where the cleaned-up output ends.

• read visits every element.
• write marks the boundary: everything left of it is finished output.
• When read finds an element worth keeping, copy it to position write and advance write.

One pass, O(n) time, O(1) space. Remove-duplicates-from-sorted-array, move-zeros, and remove-element are all this exact loop with a different "worth keeping" test.