rust_dsa_pattern_textbook.md

Rust DSA Pattern Textbook (Blind75 + NeetCode150)

This is the long-form companion to:

• rust_dsa_pattern_cheatsheet.md

Use this document when you want to understand why a pattern works, not just how to type it.

---

1) Mental Model: Pattern Before Code

In DSA interviews, most problems are not asking for brand-new algorithms. They ask whether you can map a prompt to a known family:

• Lookup/frequency problems -> hash maps/sets
• Sorted constraints -> binary search or two pointers
• Contiguous window with constraints -> sliding window
• Parentheses / nearest greater -> stacks
• Reachability -> BFS/DFS
• Optimization over choices -> dynamic programming or greedy

A reliable process:

1. Identify input structure: array, string, linked list, tree, graph, interval list.
2. Identify objective: existence, count, min/max, enumeration, reconstruction.
3. Identify constraints: sorted? bounded values? small n? repeated queries?
4. Pick the smallest pattern that satisfies correctness + complexity.

---

2) Arrays and Hashing

When to use

Use hashing when you need O(1)-average membership, counts, or complement lookups.

Typical prompts:

• "contains duplicate"
• "find pair that sums to target"
• "group by signature" (anagrams)
• "first unique / frequency"

Core invariants

• HashSet: each element appears at most once.
• HashMap<K, V>: exactly one value per key, usually count/index/state.

Why it works

Many O(n^2) brute-force loops repeatedly ask membership questions. Hashing memoizes those questions so each check is O(1)-average.

Rust notes

• Counting idiom: *map.entry(x).or_insert(0) += 1;
• For strings, decide key type early (String, Vec<u8>, or fixed-size signature arrays).
• If sums can exceed i32, promote to i64.

Complexity

• Time: O(n) average
• Space: O(n)

---

3) Two Pointers

When to use

Use when a monotonic movement in one or both directions can discard impossible states.

Typical prompts:

• sorted pair sum
• in-place dedupe in sorted array
• palindrome checks
• 3Sum after sorting

Core invariants

• Window or pair boundaries only move forward (or inward), never back.
• Every move preserves search completeness (no valid answer is skipped).

Why it works

On sorted inputs, pointer movement corresponds to predictable changes in value. You can rule out whole ranges in one step.

Rust notes

• Be careful with usize underflow on r -= 1.
• Prefer while l < r and initialize r = n - 1 only when n > 0.

Complexity

• Time: usually O(n) after sorting (if needed, total O(n log n))
• Space: O(1) extra (excluding output)

---

4) Sliding Window

When to use

Use when the answer is about a contiguous range and constraints can be maintained incrementally.

Typical prompts:

• longest substring with condition
• minimum window containing condition
• at most k distinct
• fixed-size maximum sum

Core invariants

• Window [l, r] represents the current candidate.
• Data structure (counts/frequency) exactly reflects elements in current window.
• If invalid, move l until valid again.

Why it works

Each pointer moves at most n times, so even nested while loops remain linear overall.

Rust notes

• Strings: avoid direct indexing by byte unless ASCII-safe. Use as_bytes() when problem guarantees uppercase/lowercase English letters.
• Remove zero counts from maps to keep distinct-size checks accurate.

Complexity

• Time: O(n)
• Space: O(k) or O(alphabet)

---

5) Monotonic Stack

When to use

Use when you need nearest greater/smaller elements or when elements are resolved in one direction.

Typical prompts:

• next greater element
• daily temperatures
• largest rectangle in histogram

Core invariants

• Stack maintains monotonic ordering (increasing or decreasing values/indexes).
• Each index is pushed once and popped once.

Why it works

The stack stores unresolved candidates. A new element resolves all previously waiting elements that it dominates.

Rust notes

• Store indices in stack, not values, to compute distances.
• Pattern: while let Some(&j) = st.last() { ... }

Complexity

• Time: O(n)
• Space: O(n)

---

6) Binary Search

When to use

Use when the search space is ordered and a predicate is monotonic (false...false, true...true).

Typical prompts:

• target in sorted array
• first/last position
• minimum feasible speed/capacity/day

Core invariants

• Use half-open interval [lo, hi) whenever possible.
• Maintain meaning: answer is always in current interval.

Why it works

Each step halves the search space while preserving the invariant.

Rust notes

• Midpoint: lo + (hi - lo) / 2.
• For "binary search on answer", predicate must be monotonic; prove this first.

Complexity

• Time: O(log n)
• Space: O(1)

---

7) Linked Lists

When to use

Use pointer rewiring patterns for reverse/merge/remove/cycle operations.

Typical prompts:

• reverse list
• merge sorted lists
• remove nth from end
• cycle detection
• reorder list

Core invariants

• Keep stable handles (prev, cur, next) during rewiring.
• Dummy head simplifies edge cases near the real head.

Why it works

Pointer operations are local; correctness depends on not losing next references.

Rust notes

• Option<Box<ListNode>> rewiring needs take() to move ownership safely.
• For custom Rc/RefCell variants, keep borrow scopes short.

Complexity

• Time: O(n)
• Space: O(1) iterative, O(n) recursive stack if recursion used.

---

8) Trees

When to use

Use DFS for path/structure computations and BFS for level-wise behavior.

Typical prompts:

• depth/diameter/path sum
• BST validation / kth smallest
• level order / right side view
• serialize/deserialize

Core invariants

• DFS returns a well-defined summary for subtree (height, validity, best path, etc.).
• BFS queue contains exactly current frontier.

Why it works

Trees are recursively defined; post-order DFS naturally composes child summaries.

Rust notes

• Standard LC shape: Option<Rc<RefCell<TreeNode>>>.
• Clone Rc as needed, but avoid holding mutable and immutable borrows simultaneously.

Complexity

• Most traversals: O(n) time, O(h) recursion stack (or O(w) queue for BFS).

---

9) Graphs

When to use

Use graph traversals for connectivity, shortest path, ordering, and component counts.

Typical prompts:

• number of islands/components
• course schedule (topological sort)
• shortest path unweighted/weighted

Core pattern map

• Unweighted shortest path -> BFS
• Weighted nonnegative shortest path -> Dijkstra
• DAG ordering -> Kahn DFS/toposort
• Connectivity -> DFS/BFS/DSU

Why it works

Graph algorithms are distinguished by edge semantics (weighted vs unweighted, directed vs undirected, cyclic vs DAG).

Rust notes

• Dijkstra min-heap: BinaryHeap<(Reverse<dist>, node)>.
• For large sparse graphs, adjacency list (Vec<Vec<(to, w)>>) is standard.

Complexity

• BFS/DFS: O(V + E)
• Dijkstra with heap: O((V + E) log V)
• Kahn topo: O(V + E)

---

10) Backtracking

When to use

Use when output requires enumerating combinations/permutations/partitions under constraints.

Typical prompts:

• subsets/permutations
• combination sum
• palindrome partitioning
• N-Queens

Core invariants

• path is always a valid partial construction.
• Each recursive frame chooses one decision, explores, then undoes it.

Why it works

Depth-first enumeration with pruning avoids generating impossible branches.

Rust notes

• Clone path only at result push.
• Keep mutable vectors reused across recursion for performance.

Complexity

• Exponential in general; pruning quality determines practical speed.

---

11) Dynamic Programming

When to use

Use when the problem has overlapping subproblems + optimal substructure.

Typical prompts:

• count ways
• max/min achievable value
• edit distance / LCS
• decode/partition/interleaving

Core formulation

1. Define state (dp[i], dp[i][j], etc.)
2. Define transition from smaller states
3. Initialize base cases
4. Choose fill order consistent with dependencies

Why it works

Memoization/tabulation ensures each state is solved once.

Rust notes

• Use Vec with sentinel values (-1, i32::MAX/2, etc.) for clear unreachable states.
• Prefer iterative tabulation where recursion depth may overflow.

Complexity

• Time/space depend on number of states × transitions per state.

---

12) Greedy

When to use

Use when a local best choice can be proven to extend to global optimum.

Typical prompts:

• jump game reachability
• interval scheduling
• gas station
• merge/partition style linear scans

Proof mindset

You must justify greedy with one of:

• exchange argument
• staying-ahead argument
• cut property

If proof is unclear, DP may be safer.

Complexity

• Often O(n) or O(n log n) if sorting required.

---

13) Intervals

When to use

Use for overlap, merging, scheduling, and room-count questions.

Typical prompts:

• merge intervals
• insert interval
• erase overlap
• meeting rooms

Core invariants

• Sort by start time first.
• Keep current merged interval and either extend or flush.

Complexity

• O(n log n) for sorting + O(n) sweep.

---

14) Bit Manipulation

When to use

Use for parity, uniqueness, masking, counting bits, or arithmetic constraints.

Typical prompts:

• single number
• hamming weight
• reverse bits
• sum without plus

Core identities

• x & (x - 1) removes lowest set bit.
• x ^ x = 0, x ^ 0 = x (XOR cancellation).
• Left/right shifts correspond to multiply/divide by powers of two (with sign caveats).

Rust notes

• Be explicit about integer types before bit ops.
• For bit count loops, avoid undefined assumptions about signed shifts.

---

15) DSU (Union-Find)

When to use

Use for dynamic connectivity queries and cycle checks in undirected graphs.

Typical prompts:

• number of components
• redundant connection
• graph valid tree checks

Core invariants

• Each set has a representative root.
• find with path compression flattens tree.
• union by size/rank keeps trees shallow.

Complexity

• Amortized near O(1) per operation, formally O(alpha(n)).

---

16) Debugging Framework (Practical)

When a solution fails:

1. State invariant in one sentence.
2. Add asserts/logs at every mutation that should preserve invariant.
3. Minimize failing test to smallest counterexample.
4. Re-check edge cases:
   • empty input
   • single element
   • all equal
   • strictly increasing/decreasing
   • max/min numeric bounds

This process is usually faster than randomly patching code.

---

17) Rust-Specific Performance and Safety Notes

• Prefer as_bytes() for ASCII string problems.
• Keep borrows short around RefCell.
• Avoid repeated cloning of big vectors in recursion loops.
• Use sort_unstable() when order stability is irrelevant.
• Promote to i64 for accumulation to avoid overflow bugs.
• For heaps requiring min behavior, wrap with Reverse.

---

18) Study Strategy With This Repo

Suggested loop:

1. Read quick trigger in cheat sheet.
2. Read matching section in this textbook file.
3. Implement one problem.
4. Write 1-2 notes under /// ## Notes and /// ## Complexity in the problem file.
5. Run:
   • make template-check
   • make solved-sync
   • make progress

This compounds understanding instead of just memorizing templates.