DSA Pattern Sheet

Learn DSA by pattern: hashing, two pointers, sliding window, prefix sum, binary search, trees, graphs and DP, with the problems that use each one.

DSA patterns

• Hashing & counting: Trade memory for speed: remember what you have seen.
• Two pointers: Walk two indices through the data instead of nesting loops.
• Sliding window: Grow and shrink a window over a contiguous range.
• Prefix sum: Precompute running totals so any range sum is instant.
• Kadane & running best: Carry the best answer ending here as you scan once.
• Binary search: Halve a sorted or monotonic search space every step.
• Binary search on the answer: Binary-search the answer itself, checking each guess.
• Intervals: sort & sweep: Sort by start (or end) and sweep once.
• Matrix traversal: Walk a grid in a fixed order with careful boundaries.
• Stack: Last in, first out: undo, match and evaluate.
• Monotonic stack: Keep a sorted stack to find next greater/smaller fast.
• Linked list: pointers & fast-slow: Rewire next pointers; use a fast and a slow runner.
• Tree DFS (recursion): Solve a subtree, then combine the answers upward.
• Tree BFS (level order): Process the tree one level at a time with a queue.
• Binary search tree: Use the left < node < right rule to prune the search.
• Heap & top-K: Keep only the best K, or the next best, in a heap.
• Greedy: Take the locally best choice and never look back.
• Graph BFS/DFS & grids: Visit every reachable cell or node exactly once.
• Topological sort: Order tasks so every prerequisite comes first.
• Union-Find: Merge groups and ask "same group?" in near-constant time.
• Shortest path: Always expand the cheapest known node (Dijkstra).
• Backtracking: Build choices step by step; undo them when stuck.
• DP: 1D: Each answer is built from a few earlier answers.
• DP: grids & 2D: Fill a table where each cell depends on its neighbours.
• DP: knapsack & subsets: For each item, take it or skip it within a capacity.
• DP: strings (LCS, edit distance): Compare two strings prefix by prefix in a table.
• Trie: Store words by shared prefixes in a tree of characters.
• Bit manipulation: Use XOR, AND and shifts to work on bits directly.