mediumGraphsPattern: Topological Sort
Task Dependency Order Solution
Problem Statement
Given a set of tasks and their dependencies, where each task must be completed before other dependent tasks can begin, find a valid sequence of task completion that satisfies all dependencies. Each task is represented by a unique integer ID. The dependencies are provided as a list of pairs `[dependent_task, prerequisite_task]`, indicating that `prerequisite_task` must be completed before `dependent_task`.
Examples
Example 1:
Input:{"numTasks":4,"dependencies":[[1,0],[2,0],[3,1],[3,2]]}
Output:[0,1,2,3]
Explanation: Task 0 has no prerequisites. Tasks 1 and 2 depend on Task 0. Task 3 depends on both Task 1 and Task 2. A valid order is to complete Task 0 first, then Task 1 and Task 2 (in any order relative to each other), and finally Task 3.
Example 2:
Input:{"numTasks":3,"dependencies":[[1,0],[0,1]]}
Output:[]
Explanation: There is a circular dependency between Task 0 and Task 1 (Task 1 depends on Task 0, and Task 0 depends on Task 1). It's impossible to complete these tasks, so an empty list is returned.
Example 3:
Input:{"numTasks":2,"dependencies":[[1,0]]}
Output:[0,1]
Explanation: Task 1 depends on Task 0. Task 0 must be completed first.
Constraints
- 1 <= numTasks <= 2000
- 0 <= dependencies.length <= numTasks * (numTasks - 1) / 2
- 0 <= dependent_task, prerequisite_task < numTasks
- dependencies[i] != dependencies[j] for all i != j
- The graph may contain cycles.
Time: O(V + E) Space: O(V + E)
Represent the tasks and dependencies as a directed graph where an edge from task A to task B means A must be completed before B. Use Kahn's algorithm (based on in-degrees) or DFS to find a topological sort. If a cycle is detected (e.g., by not being able to process all tasks), return an empty list.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
from typing import List
def find_order(numTasks: int, dependencies: List[List[int]]) -> List[int]:
adj = [[] for _ in range(numTasks)]
in_degree = [0] * numTasks
for dest, src in dependencies:
adj[src].append(dest)
in_degree[dest] += 1
queue = []
for i in range(numTasks):
if in_degree[i] == 0:
queue.append(i)
order = []
while queue:
task = queue.pop(0)
order.append(task)
for neighbor in adj[task]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return order if len(order) == numTasks else []