Two Pointers
Two pointers use two indices (often left and right) moving through an array to eliminate nested loops and achieve O(n) solutions.
Two pointers = two people searching a hallway from opposite ends. They walk toward each other, checking every door. They never backtrack, so they cover the whole hallway in one pass.
Two flavors: (1) opposite ends — start left=0, right=n-1 and move inward (e.g., two-sum on sorted array, three-sum, container with most water); (2) same direction — fast/slow or leading/trailing (e.g., remove duplicates in-place, merge sorted arrays). Precondition for opposite-end two pointers is usually a sorted array or monotonic property. The key insight: at each step you have enough information to decide which pointer moves.
The mathematical argument for correctness: if you have two pointers at i and j, and you know that moving i rightward can only decrease (or increase) your target metric, you can eliminate all pairs involving i at its current position, giving O(n) total moves. This is the same argument that justifies why binary search works. Extension: three-sum is O(n²) — sort first (O(n log n)), fix one pointer, run two-pointer on the rest. For two-sum without sorting, a hash map is O(n) time and O(n) space — know when to prefer which.
Two pointers turn O(n²) into O(n) by leveraging a monotonic property — usually that the array is sorted or that moving a pointer in one direction monotonically changes the quantity you care about. I'd reach for two pointers when the problem involves pairs or subarrays in a sorted structure, or when I need to modify an array in-place (e.g., remove duplicates). The critical step is proving why I can safely eliminate all arrangements that include the current pointer position when I decide to advance.
Opposite-end two pointers require a sorted array or equivalent monotonic property. Applying them to an unsorted array without justification is incorrect. Also: when fixing elements for three-sum, remember to skip duplicates to avoid duplicate triplets in the output.