Where it runs
1. The problem
You are getting dressed. Socks before shoes. Shirt before jacket. Underwear before trousers. None of these rules says "do me third". Each one only says "do me after that other one". Your job is to find a full order that breaks none of the rules.
Software does this all the time. A package manager installs libraries, and a library has to go in after everything it needs. A build tool compiles files, and one file imports another. A course list has courses you must take first. Each case asks the same thing: given a pile of "X must come before Y" rules, give one order that keeps all of them.
Sometimes there is no such order. If A needs B and B needs A, no order works. A good tool has to notice that and say so, instead of running forever.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedtopoSort(6, [[1, 2], [3], [3, 5], [4, 5], [], []])An arrow u → v means u has to run before v. Count the arrows coming into each task.
Recognise it
Say these words and it is this pattern
- task must come before another
- order that respects dependencies
- detect a cycle in prerequisites
- build order / course schedule / install order
- directed graph, X must happen before Y
Looks similar, isn't
- Graph BFS / DFS
A plain walk visits every node in whatever order it likes. Here the order is the answer.
- Connected components
Components ignore direction and only group nodes. Here direction defines the whole answer.
- Union-find (disjoint set)
Union-find treats every edge as undirected. Direction is exactly what matters here.
- Greedy (exchange argument)
The rule is greedy: take anything with no debts left. Removing a node can never add a dependency.
V nodes and E edges give O(V + E). Every edge is removed exactly once.
On LeetCode
Problems that put tasks in an order that respects dependencies, or say no order exists. Count incoming edges, start from the nodes with zero, and remove them one by one, and if some nodes are never reached there is a cycle.
The lesson's topoSort under another name, returning an empty list instead of null when there is a cycle.
Each ingredient points to the recipes that need it, the supplies go into the queue first, and a recipe can be made once its count of missing ingredients reaches zero.
Walk in topological order and pass each course's set of prerequisites to the courses after it, then answer each query from the sets.
Run two separate topological sorts, one for row conditions and one for column conditions, and place each number at its two positions.