Does this diamond prevent progress?

A→B, A→C, B→D, C→D.

First read arrows as prerequisites. Then erase their direction and read them as physical connections.

Why do the two cycle questions have different answers?

1 / 9

Number of Islands — predict before coding

Recognize a component-counting problem when the answer counts groups rather than cells. Four-neighbor adjacency is the graph; diagonal contact does not connect land. The outer scan chooses one representative per component, and a complete flood fill prevents any other cell in that component becoming a new representative.

Decision: For rows 110 / 010 / 001, how many islands are there? Which cell would be counted twice if a component were only partly marked?

Presenter notes

Model answer: There are two islands. The first contains (0,0), (0,1), and (1,1); (2,2) is separate because diagonal contact does not count. Failing to reach (1,1) from the first representative would incorrectly create a third count when the scan reaches it.

Correctness argument: When the outer scan reaches an unmarked land cell, no previously counted component contains it: any such component would already have marked every cell reachable by a land path. The stack starts at this new representative. Every pushed cell is connected to it, and marking on push ensures a cell is pushed at most once. Conversely, induction along a land path shows every cell in its component is eventually reached. Thus one increment accounts for exactly one previously uncounted component. After the scan every original land cell belongs to exactly one counted component.

Debugging prompt: Log each count increment and all cells it claims. Mark when pushing, not after popping; otherwise several neighbors can queue the same land cell. Copy the grid before calling when the caller needs the original map.

2 / 9

Surrounded Regions — predict before coding

Invert the difficult question. Instead of trying to prove each region enclosed, first prove which O cells can escape to the border. The complement is precisely the set to capture.

Decision: Why does an interior O connected by a narrow O corridor to one border cell survive, even when most of its neighbors are X?

Presenter notes

Model answer: Survival is reachability, not a count of neighboring X cells. The corridor is a valid escape path, so flood fill from its border endpoint reaches and protects the entire attached region.

Correctness argument: The initial queue contains all border O cells, marked safe before insertion. Every subsequently marked cell is an O neighbor of a safe cell, so it has an O-only path to the border. Conversely, for any O cell with such a path, induction along that path from the border shows flood fill marks it. Therefore marked cells are exactly the border-connected O set. The final scan restores precisely those cells to O and changes every other original O to X. No X ever enters the queue, so barriers and the rectangular shape are preserved.

Debugging prompt: Test a one-row board, one-column board, and a winding escape corridor. Count-based local rules cannot establish enclosure. Temporary S markers must all disappear before return.

3 / 9

Clone Graph — predict before coding

A deep copy preserves topology, sharing, cycles, and adjacency order while replacing every node identity. The map is not merely visited state: it is the correspondence between the two graphs.

Decision: In a triangle A-B-C-A, why must A be entered in the clone map before recursively copying B?

Presenter notes

Model answer: The recursion can return to A through C. Without the early map entry it allocates another A and recurses forever. With the entry, that edge points to the first clone of A, closing the copied cycle correctly.

Correctness argument: On the first encounter with an original node, allocate exactly one clone and record it before exploring neighbors. Every later encounter returns that same clone, so cycles terminate and two references to one original remain two references to one clone. For every adjacency entry u->v, append the mapped clone of v to the clone of u in the original order. Induction over first discoveries constructs all reachable nodes; revisits preserve established identities. All allocated nodes are fresh, and no original field is written, so the result is disjoint from the source and preserves its entire reachable adjacency structure.

Debugging prompt: Compare node identity as well as values. A shallow copied neighbor slice still points to originals. Preserve neighbor order rather than sorting it, and verify the source graph is unchanged.

4 / 9

Evaluate Division — predict before coding

This is path-product reachability, not a weighted shortest-path problem. Store a/b on edge a->b and its reciprocal on b->a; multiplying ratios along a path cancels intermediate variables.

Decision: Given a/b=2 and b/c=3, what should queries a/c, c/a, a/a, and unknown/unknown return?

Presenter notes

Model answer: They return 6, 1/6, 1, and -1. The final query is unknown despite the algebraic identity because the variable never appears in the known system.

Correctness argument: Every queued state (v,p) has p equal to the product along a discovered source-to-v path. It is true initially with product 1 at the source and remains true after multiplying by an outgoing edge. Under consistent nonzero finite equations, all paths between the same pair describe the same ratio, so one visit per variable suffices; there is no optimization over competing weights. Reaching the destination yields the required ratio. Exhausting the reachable component proves no relation can be inferred. Membership is checked before the self-query shortcut: an unknown x does not make x/x a known equation.

Debugging prompt: Check reciprocal orientation and reset visited state per query. A globally reused visited set can make a later valid query fail. Floating results need tolerance, not string equality.

5 / 9

Course Schedule — predict before coding

A prerequisite pair [a,b] is a directed edge b->a. A course becomes available when all incoming requirements have been removed, not merely when one predecessor has finished.

Decision: For prerequisites [1,0], [2,0], [3,1], [3,2], when does course 3 become available?

Presenter notes

Model answer: Only after both 1 and 2 have been processed. Its residual indegree goes 2->1->0; the first decrement is not enough. Course 0 starts available, and isolated courses must also enter the initial queue.

Correctness argument: Maintain indegree as the number of incoming edges from unprocessed vertices. It is correct initially by construction. Removing a queued zero-indegree vertex satisfies exactly its outgoing dependencies, so decrementing each corresponding target preserves the invariant. Every emitted vertex is therefore schedulable after the emitted prefix. If vertices remain and none has zero indegree, repeatedly following a remaining incoming edge in the finite residual graph eventually repeats a vertex, proving a directed cycle. Conversely, a cycle can never lose all its internal incoming dependencies. Hence processing all vertices is equivalent to feasibility.

Debugging prompt: Draw arrows before building arrays. Count every edge consistently in both indegree and adjacency. Include isolated vertices and a disconnected cyclic component in tests.

6 / 9

Course Schedule II — predict before coding

The output is a certificate, not a unique sequence. Validate a topological order by checking it contains every course once and places each prerequisite before its dependent.

Decision: For courses 0,1,2 with only edge 0->2, are [0,1,2] and [1,0,2] both valid? What must a test check instead of one fixed order?

Presenter notes

Model answer: Both are valid. A test must check length three, no duplicates, all labels in range, and position(0)<position(2). Exact equality with a preferred ordering would reject correct solutions.

Correctness argument: The queue contains exactly currently available unprocessed courses. By the residual-indegree invariant, each appended course has no unmet dependency, so every prefix respects all prerequisite edges whose targets have been emitted. When all vertices are appended, the order is a complete valid certificate. If fewer than numCourses are appended, a residual directed cycle prevents a complete certificate, so returning a partial prefix would be misleading and the function returns an empty result. Ties between available vertices may be resolved in any order without affecting correctness.

Debugging prompt: Keep cycle detection separate from tie ordering. A nonempty prefix from a cyclic graph is not a valid answer. Validate the returned certificate against every original edge.

7 / 9

Redundant Connection — predict before coding

Union-find summarizes connectivity of the edges already accepted. Adding an edge inside one connected component closes a cycle; adding one between components joins them safely.

Decision: For edges [1,2], [2,3], [1,3], which edge is rejected? Why would simply comparing the two immediate parent array entries be unsafe?

Presenter notes

Model answer: [1,3] is rejected. Connectivity is equality of representatives returned by find, not necessarily equality of immediate parent pointers; a node can be several links below its representative.

Correctness argument: Initially every vertex is its own component. By induction, union operations make two vertices share a representative exactly when accepted edges connect them. If a new edge has different representatives, joining it cannot form a cycle, and union preserves the invariant. If its endpoints already share a representative, the accepted graph contains a path between them, so the new edge closes a cycle. Under the tree-plus-one-edge contract there is exactly one cycle; the detected edge is the last edge of that cycle in input order, and removing it leaves a connected acyclic graph. This argument is not a detector for arbitrary directed cycles.

Debugging prompt: Test a long chain closed by its final edge and a cycle whose last input edge is not the originally added edge in your drawing. Preserve the original orientation of the returned pair.

8 / 9

What information must survive a visit?

Compare three tasks on a cyclic graph: count reachable vertices, clone every edge, and return a ratio along a path.

For each, specify what a visited boolean omits and what state you would retain.

9 / 9