OneNoughtOne
0/97
Loading content...
You are given a set of numTasks tasks that need to be executed, labeled from 0 to numTasks - 1. Some tasks have prerequisite dependencies, meaning certain tasks must be completed before others can begin.
You are provided with an array dependencies where each element dependencies[i] = [taskA, taskB] indicates that task taskB must be completed before task taskA can be started.
Your goal is to determine a valid execution order that allows all tasks to be completed while respecting all dependencies. If multiple valid orderings exist, return any one of them. If it is impossible to complete all tasks due to circular dependencies, return an empty array.
For a dependency pair [taskA, taskB]:
Dependency Graph: The tasks and their dependencies form a directed graph where an edge from taskB to taskA means "taskB must come before taskA"
Valid Ordering: A valid task execution order is one where every task appears after all of its prerequisites in the sequence
Cycle Detection: If the dependency graph contains a cycle (e.g., Task A depends on B, B depends on C, C depends on A), then no valid ordering exists
Multiple Solutions: When there's no dependency between two tasks, they can appear in any relative order, leading to multiple valid solutions
numTasks = 2
dependencies = [[1,0]][0,1]Explanation
There are 2 tasks to complete. Task 1 depends on Task 0, meaning Task 0 must be finished first. The only valid execution order is [0, 1] — complete Task 0, then Task 1.
numTasks = 4
dependencies = [[1,0],[2,0],[3,1],[3,2]][0,1,2,3] or [0,2,1,3]Explanation
There are 4 tasks. Task 1 and Task 2 both depend on Task 0. Task 3 depends on both Task 1 and Task 2. Therefore, Task 0 must come first, followed by Tasks 1 and 2 in any order, and finally Task 3. Valid orderings include [0,1,2,3] and [0,2,1,3].
numTasks = 1
dependencies = [][0]Explanation
There is only one task with no dependencies. Simply return [0] as the execution order.
Constraints