Rust Questions

Top 30 LeetCode Questions in Rust

Problem	Type	Key Pattern	Rust Idiom	Rust Book Chapter	Notes and Suggestions
207	Graph	Topological Sort (Kahn's)	Vec<Vec<i32>> + VecDeque	Ch 8, 13	Remember why VecDeque is suitable for the queue in Kahn's algorithm.
133	Graph	Deep Clone	HashMap<i32, Rc<RefCell<Node>>>	Ch 15	Pay attention to ownership and mutability managed via Rc and RefCell.
787	Graph	Bellman-Ford	(i32, usize) in Vec	Ch 6, 8	Consider edge cases and the relaxation step in Bellman-Ford.
200	Graph	Grid DFS	&mut Vec<Vec<char>> mutation	Ch 4	Be mindful of the borrow checker during in-place grid modifications.
547	Graph	Union-Find	parent: Vec<usize> with path compression	Ch 8	Understand the benefits of path compression and rank optimisation.
743	Graph	Dijkstra's	BinaryHeap<Reverse<(i32, usize)>>	Ch 13, 19	Know why Reverse is used to simulate a min-heap.
417	Graph	Multi-source DFS	(bool, bool) matrix + recursive closure	Ch 13	Consider how multiple sources influence DFS initialisation.
332	Graph	Eulerian Path	HashMap<_, Vec<_>> + lexical sort	Ch 8, 17	Know the conditions under which an Eulerian path exists.
1584	Graph	Kruskal's MST	Vec<(i32, usize, usize)> + sort	Ch 13	Familiarise yourself with Kruskal’s greedy algorithm.
684	Graph	Cycle Detection	Union-Find with early return	Ch 8	Use Union-Find effectively to detect cycles.
98	Tree	BST Validation	Option<&Rc<RefCell<TreeNode>>> with bounds	Ch 15	Handle edge cases and recursive bound propagation.
105	Tree	Pre/In-order Build	Slice patterns [first..mid], [mid+1..]	Ch 4	Understand how the two traversals uniquely define the tree.
236	Tree	LCA	Option pattern matching	Ch 6, 15	Know the recursion base cases and LCA identification logic.
102	Tree	Level-order	VecDeque<Rc<RefCell<TreeNode>>>	Ch 13	VecDeque is ideal for Breadth-First Search (BFS).
199	Tree	Right View	BFS with level tracking	Ch 8	Modify BFS to capture the rightmost node at each level.
543	Tree	Diameter	Rc<RefCell<i32>> global max	Ch 15	The diameter may not always pass through the root.
124	Tree	Max Path Sum	i32::MIN initialisation	Ch 6	Handle negative nodes and ensure robust base cases.
297	Tree	Serialisation	String::split + VecDeque	Ch 8, 17	Consider empty trees and the format of serialisation.
652	Tree	Duplicate Subtrees	HashMap<String, _>	Ch 8	Represent subtrees as strings for efficient comparison.
114	Tree	Flatten to List	In-place take() of left/right	Ch 15	take() helps move ownership out of Option.
322	DP	Coin Change	Vec<usize> bottom-up DP	Ch 8	Start with base case (amount 0) and build up.
1143	DP	LCS	2D Vec<Vec<usize>>	Ch 8	Understand the recurrence relation in the 2D table.
300	DP	LIS	Vec::binary_search	Ch 13	Binary search optimises to O(n log n) time.
5	DP	Palindromic Substring	Expand-around-centre	Ch 4	Account for both even and odd-length palindromes.
139	DP	Word Break	Vec<bool> + slice windows	Ch 8	Track prefix segmentations with a DP array.
416	DP	Partition Subset	Bitmask Vec<bool>	Ch 8	Track whether a subset sum equals the target.
62	DP	Unique Paths	Combinatorics	Ch 3	Use mathematical combinations for efficiency.
198	DP	House Robber	prev/curr tuple tracking	Ch 6	Optimise space by keeping only two prior states.
64	DP	Min Path Sum	In-place grid updates	Ch 8	Reuse the grid to save space for the DP table.
312	DP	Burst Balloons	Vec<Vec<i32>> interval DP	Ch 8	Focus on state definition and transitions.

---

Key Rust Book Chapters to Revise

• Chapter 4: Ownership

  • Crucial for understanding Rust's memory model.
  • Fundamental when dealing with recursive structures like trees and graphs.

• Chapter 8: Collections

  • Covers Vec, HashMap, VecDeque—core to nearly all problems.

• Chapter 13: Iterators

  • Leads to more idiomatic Rust, especially for traversal and filtering logic.

• Chapter 15: Smart Pointers

  • Essential for shared ownership and interior mutability (Rc, RefCell).

• Chapter 17: Object-Oriented Programming

  • Useful for traits and abstraction, helpful in complex designs.