20 Essential DSA Patterns

Use two positions to narrow a search in a sorted sequence or compare opposite ends. Explain why each pointer can move safely.

Watch for: Do not discard candidates before establishing the ordering invariant.

Maintain a contiguous range while updating a small state as its boundaries move. Distinguish fixed-size windows from variable-size windows.

Watch for: Negative numbers can invalidate a sum-based shrinking rule.

Move pointers at different speeds to find cycles or locate the middle of a linked structure.

Watch for: Check null boundaries before advancing the fast pointer twice.

Store cumulative totals to answer range queries or count subarrays using differences between prefixes.

Watch for: Include the empty prefix and distinguish counts from earliest positions.

Map values to counts, positions or groups when repeated lookup would dominate the runtime.

Watch for: State the expected lookup complexity and additional memory cost.

Sort ranges and reason about overlap, merging, insertion or scheduling.

Watch for: Clarify whether endpoints that touch count as overlapping.

Use a value’s expected index or an index-addressed marker to detect missing and repeated values in a bounded range.

Watch for: Validate the value range before using a number as an array index.

Discard a proven impossible half of a sorted space or search for the boundary of a monotonic condition.

Watch for: Define the interval convention and show that every iteration makes progress.

Keep candidates in increasing or decreasing order to answer next-greater or next-smaller queries.

Watch for: Explain when equal values should be removed and how widths are calculated.

Rewire a chain while preserving the next node before changing pointers. Extend the invariant to segments or groups.

Watch for: Avoid losing the unprocessed suffix or creating an accidental cycle.

Use recursion or an explicit stack when answers depend on subtrees, root-to-leaf paths or postorder combinations.

Watch for: Separate the value returned to a parent from a global best answer.

Explore by distance or level with a queue. Use multiple starting points when waves expand from several sources.

Watch for: Mark visited when enqueuing to avoid duplicate work.

Build a partial solution, choose a candidate, recurse, and restore state before the next choice.

Watch for: Define a pruning rule and avoid adding mutable references to the answer.

Keep the best candidates in a priority queue or merge sorted streams by repeatedly taking their next smallest item.

Watch for: Decide whether the heap should retain the largest K or smallest K values.

Represent relationships using adjacency lists or a grid and visit reachable states with DFS or BFS.

Watch for: Handle disconnected components and specify whether edges are directed.

Order prerequisite relationships in a directed acyclic graph using indegrees or DFS finishing order.

Watch for: Detect cycles rather than returning an incomplete order as a valid answer.

Maintain connected components with representative parents, path compression and size or rank balancing.

Watch for: Use a directed-graph algorithm when direction is essential to the problem.

Define a state, transition and base case for overlapping subproblems before optimizing storage.

Watch for: Explain the meaning of each state and the iteration order it requires.

Commit to a locally optimal decision only when an exchange argument or invariant supports it.

Watch for: Test tempting greedy rules against a small counterexample before coding.

Use bitwise identities for parity, compact state, masks and counting set bits.

Watch for: Clarify integer width and signed-shift behavior in your language.