Search patterns

20 patterns

1. Frequency Map

   Count or index values so repeated scanning becomes direct lookup.

2. Two Pointers

   Move two indices under an invariant to avoid testing every pair.

3. Sliding Window

   Maintain just enough state for a contiguous range as its boundaries move.

4. Prefix Sum

   Precompute cumulative state so range totals or balanced prefixes are cheap.

5. Binary Search

   Maintain an ordered search interval and discard half on each step.

6. Stack

   Keep unresolved items in last-in-first-out order.

7. Fast & Slow Pointers

   Advance pointers at different rates to reveal cycles or midpoints.

8. BFS

   Explore a graph level by level with a queue.

9. DFS

   Explore one branch fully before backtracking.

10. Topological Sort

    Order directed dependencies while detecting cycles.

11. Union Find

    Maintain connected components under repeated merges.

12. Backtracking

    Choose, explore, and undo while pruning invalid partial solutions.

13. Heap Selection

    Keep the best k candidates or next priority available incrementally.

14. Trie

    Traverse character prefixes through a tree-shaped index.

15. 1D DP

    Build answers along one state dimension from previously solved positions.

16. 2D DP

    Track two changing dimensions such as grid position or paired prefixes.

17. Merge Intervals

    Sort ranges, then combine or select them using endpoint relationships.

18. Monotonic Stack

    Maintain candidates in increasing or decreasing order for nearest-boundary queries.

19. Greedy

    Commit to a local choice backed by a global invariant or exchange argument.

20. Bit Manipulation

    Use masks, shifts, and XOR identities to represent or transform state.