The One Valid Build Order (DFS)
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. Return an order in which all tasks can be done. In this version the dependencies are so tight that only one order is possible, so every correct method returns the same list.
The depth-first approach records each task when the search is completely done with it; the reverse of that list is a valid order (a topological 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, and the tasks can be arranged in exactly ONE valid order (every task is forced by the roads) - ◆
A valid order lists all tasks so that for every road u → v, task u appears before task v - ◆
Return that order
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Every Ordering of the Tasks
BruteGenerate the orderings of all n tasks one by one and, for each finished ordering, check every road u → v: if some road goes backwards (v before u) the ordering is invalid. The first ordering that respects all the roads is returned (it is unique here). There are n! orderings, which is only possible for very small 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[] buildOrder(int[][] graph) {
28 int[] order = new int[graph.length];
29 search(graph, order, 0, new boolean[graph.length]);
30 return order;
31 }
32}Optimal — Depth-First Search, Then Reverse the Finishing Order
OptimalRun a depth-first search from every unvisited task. A task FINISHES only after everything that depends on it has finished, so a task always finishes after all tasks it points to. Record tasks in the order they finish; reading that list backwards puts every task before the tasks it points to, which is a valid order. Each task and road is handled once: O(n + E).
O(n + E)O(n)1class Solution {
2 private void visit(int[][] graph, int node, boolean[] seen, List<Integer> finished) {
3 seen[node] = true;
4 for (int next : graph[node]) {
5 if (!seen[next]) visit(graph, next, seen, finished);
6 }
7 finished.add(node);
8 }
9
10 public int[] buildOrder(int[][] graph) {
11 int n = graph.length;
12 boolean[] seen = new boolean[n];
13 List<Integer> finished = new ArrayList<>();
14 for (int start = 0; start < n; start++) {
15 if (!seen[start]) visit(graph, start, seen, finished);
16 }
17 int[] order = new int[n];
18 for (int i = 0; i < n; i++) order[i] = finished.get(n - 1 - i);
19 return order;
20 }
21}