Topic notebook / 05
Graphs & paths
Graphs can contain cycles and several ways to reach the same place. Track what is discovered and what is finalized.
What to look for
- Write down what a path score means.
- Use BFS for unweighted distances.
- Use a priority queue when better paths should be explored first.
Work through a question
10 availablePlan a Quiet Delivery
A delivery robot crosses a square floor from top-left to bottom-right. Cells marked 1 contain noisy machines. Maximize the smallest Manhattan distance to any machine along the walk. Return both the clearance and an actual route.
Medium / Multi-source BFS + heap / interactiveMeasure Connected Garden Plots
A rectangular garden map uses 1 for planted ground and 0 for walkways. Planted cells belong to the same plot only when connected up, down, left, or right. Return every plot size sorted largest first. Keep equal sizes as separate entries.
Medium / Connected components + BFS / interactiveFollow a Letter-Tile Route
Find whether a requested lowercase word can be traced on a letter board using side-sharing cells. A cell may be used only once in a route. Return true or false; diagonal steps are not allowed.
Medium / DFS backtracking / interactiveCopy a Linked Relay Network
Copy every vertex and neighbor list in an undirected adjacency-list network, including disconnected components. Return the independent copy’s adjacency lists in vertex-ID order. Neighbor order is preserved.
Medium / Identity map before recursion / interactiveCheck Workshop Prerequisites
Given {"count":n,"pairs":[[course,prerequisite],...]}, determine whether every workshop can be completed. IDs range from 0 to n-1; dependency cycles make the answer false.
Medium / Indegree elimination / interactiveRoute Water to Both Drain Edges
Water can move to an orthogonal neighbor of equal or lower height. Return cells that can drain to both top/left and bottom/right boundary groups. Sort [row,column] pairs in row-major order.
Medium / Reverse multi-source reachability / interactiveMeasure an Unbroken Badge Run
Unsorted badge IDs may repeat. Return the length of the longest run of consecutive distinct integers, regardless of input order.
Medium / Set starts without predecessor / interactiveInfer a Custom Label Alphabet
Labels arrive in a claimed alphabetic order. Infer the lexicographically smallest alphabet satisfying all observed first-difference constraints. Return "" for a cycle or a longer word before its prefix.
Hard / First-difference DAG and min-heap / interactiveAudit a Single Relay Tree
Given {"count":n,"edges":[[a,b],...]}, determine whether the undirected relay network is one connected, cycle-free tree. An empty network returns false.
Medium / Edge count plus reachability / interactiveCount Separate Relay Groups
Count connected groups in {"count":n,"edges":[[a,b],...]}. Isolated vertices count as their own groups; an empty network has zero groups.
Medium / One BFS per undiscovered component / interactiveWhere this leads
Keep following the branch when this pattern feels familiar.