Two pointers

Two pointers replace nested scans when movement rules eliminate impossible candidates. Pointers may converge from both ends, move at different speeds, or maintain a write position while reading. The pattern works best with sorted arrays, linked list cycles, partitioning, and in-place compaction.

Trade-off: compare time, memory, and implementation complexity before committing to a structure or pattern.

On interviews: Interviewers listen for the invariant that makes it safe to move one pointer instead of trying every pair.

Common pitfalls: Do not use the pattern if the input order does not support elimination. Be careful with duplicates, equality cases, and whether movement should happen before or after processing.

Checklist:

• State the elimination rule.
• Handle equality.
• Move pointers monotonically.
• Test duplicate-heavy inputs.