When to use it#
Look for the structural evidence below before naming the pattern. The constraints and invariant - not a keyword - make the choice defensible.
Recognition signals
- Prerequisites
- Build order
- Directed acyclic constraints
When another approach fits better
- Edges are undirected connectivity relationships
- You need the minimum path cost rather than a dependency order
How it works#
Try permutations and reject those that violate an edge, which is factorial in the number of nodes.
Orient each edge from prerequisite to dependent.
Count each node's remaining prerequisites.
Queue zero-indegree nodes, remove their outgoing constraints, and require the final count to equal V.
InvariantEvery node emitted by Kahn's algorithm has no remaining unmet prerequisites; processed count detects whether all nodes could be emitted.
Example and template#
Course Schedule
Recognize a feasibility question as directed-cycle detection.
Open the full problem brief- Ready
indegree 0: [A, C]Either ready node may begin a valid order.
- Emit A
decrement dependents of AA removed exactly its outgoing prerequisite constraints.
indegree = count incoming edges
queue = all nodes with indegree 0
order = []
while queue not empty:
node = dequeue
append node
for dependent in outgoing[node]:
indegree[dependent] -= 1
if indegree[dependent] == 0: enqueue
if length(order) != V: cycle- Time
- O(V + E)
- Space
- O(V + E)
- Assumptions
- The graph is represented with outgoing adjacency plus indegrees.
Pitfalls#
Common wrong approaches
Counting prerequisites on the wrong endpoint emits dependents before their requirements.
An exhausted queue before V outputs is the cycle signal.
Edge cases
- Isolated nodes
- Multiple valid orders
- Duplicate edges
- Self-cycle
Interview narration
- “I will direct edges from prerequisite to dependent.”
- “The queue contains exactly the work whose prerequisites are satisfied.”
- “If I cannot emit every node, the remaining subgraph contains a cycle.”
Practice#
Course Schedule
Recognize a feasibility question as directed-cycle detection.
Practice this problemProduce a deployment order from service prerequisites, or explain why no complete rollout is possible.
Reveal the pattern decision
This is topological ordering; incomplete processing is a cycle, not a best-effort plan.
Transfer problem
Choose the lexicographically smallest valid build order.
Checkpoint: Replace the ready queue with a min-heap without changing indegree semantics.
Follow-up variations
- Detect whether the valid order is unique
- Return one concrete cycle for diagnostics
Error-log prompts
- Which direction did each edge point?
- Did I compare emitted count with all nodes?