Patterns that turn quadratic solutions into linear ones: two pointers, sliding windows, and memoized recursion.
These techniques are reusable patterns rather than specific algorithms. Each removes repeated work from a brute-force solution: pointers and windows avoid re-scanning elements, and memoization avoids recomputing subproblems.
Two pointer keeps two indices, typically one at each end of a sorted array moving inward, or a fast and a slow pointer moving forward. Each step moves one pointer, so the total work is linear. Sliding window is a special case where both pointers bound a contiguous subarray or substring; you extend the right edge and shrink the left edge while maintaining a running sum, count or set. Memoization caches the result of each distinct recursive call; it is top-down dynamic programming and applies whenever the same subproblem is reached by many paths.
| Technique | Typical problems | Time | Extra space |
|---|---|---|---|
| Two Pointer | Pair sum in sorted array, remove duplicates, palindrome check, cycle detection | O(n) | O(1) |
| Sliding Window | Longest substring without repeats, max sum of k elements, minimum window | O(n) | O(k) or O(alphabet) |
| Recursion Memoization | Fibonacci, coin change, edit distance, grid paths | O(states x work per state) | O(states) |
If the input is unsorted and you need pairs, consider sorting first (O(n log n)) or a hash map. If memoized recursion hits Python's recursion limit, convert it to a bottom-up table. Related: Searching and Sorting.