Alphabetical Build Order (Kahn)
Solve this ProblemYou are given a set of tasks with dependencies, described as an adjacency list of a directed graph with no cycles: a road u → v means task v can only start after task u finishes. Many orders can satisfy the dependencies; return the lexicographically smallest one.
Kahn's algorithm builds the order from the front: tasks that nothing is waiting on are ready, and finishing a task may make further tasks ready. Choosing the smallest ready task each time yields the smallest order.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ n ≤ 8 tasks numbered 0 … n-1; graph[u] lists, in increasing order, every task v that can only start after task u has finished (adjacency-list form of a directed graph) - ◆
The graph has no cycles - ◆
A valid order lists all tasks so that for every road u → v, task u appears before task v - ◆
Many valid orders may exist: return the lexicographically smallest one (the first position holds the smallest possible task number, then the second, and so on)
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Orderings in Dictionary Order
BruteGenerate the orderings of the tasks in dictionary order (smallest first) and, for each one, check every road u → v: an ordering with a road going backwards is invalid. The first ordering that respects all roads is the lexicographically smallest valid one, because orderings are visited from smallest to largest. There are n! candidates, which limits it to tiny n.
O(n! · (n + E))O(n)1class Solution {
2 private boolean respectsRoads(int[][] graph, int[] order) {
3 int n = graph.length;
4 int[] position = new int[n];
5 for (int i = 0; i < n; i++) position[order[i]] = i;
6 for (int u = 0; u < n; u++) {
7 for (int v : graph[u]) {
8 if (position[u] > position[v]) return false;
9 }
10 }
11 return true;
12 }
13
14 private boolean search(int[][] graph, int[] order, int len, boolean[] used) {
15 int n = graph.length;
16 if (len == n) return respectsRoads(graph, order);
17 for (int v = 0; v < n; v++) {
18 if (used[v]) continue;
19 used[v] = true;
20 order[len] = v;
21 if (search(graph, order, len + 1, used)) return true;
22 used[v] = false;
23 }
24 return false;
25 }
26
27 public int[] smallestOrder(int[][] graph) {
28 int[] order = new int[graph.length];
29 search(graph, order, 0, new boolean[graph.length]);
30 return order;
31 }
32}Optimal — Kahn’s Algorithm With a Min-Heap
OptimalCount for each task how many tasks must come before it (its indegree). Tasks with indegree 0 are ready. Repeatedly take the SMALLEST ready task (a min-heap keeps them ordered), append it to the order, and "remove" it: decrease the indegree of every task it points to, and make a task ready when its indegree reaches 0. Always taking the smallest ready task gives the smallest order. Each task and road is processed once, with heap operations costing log n.
O((n + E) log n)O(n)1class Solution {
2 public int[] smallestOrder(int[][] graph) {
3 int n = graph.length;
4 int[] indegree = new int[n];
5 for (int u = 0; u < n; u++) {
6 for (int v : graph[u]) indegree[v]++;
7 }
8 PriorityQueue<Integer> ready = new PriorityQueue<>();
9 for (int i = 0; i < n; i++) {
10 if (indegree[i] == 0) ready.add(i);
11 }
12 int[] order = new int[n];
13 int len = 0;
14 while (!ready.isEmpty()) {
15 int u = ready.poll();
16 order[len++] = u;
17 for (int v : graph[u]) {
18 indegree[v]--;
19 if (indegree[v] == 0) ready.add(v);
20 }
21 }
22 return order;
23 }
24}