Practice/Amazon/Leetcode 210. Course Schedule II

Leetcode 210. Course Schedule II

CodingMust

Problem

You are managing a build system where certain tasks must be completed before others can begin. Given a total number of tasks (numbered from 0 to numTasks - 1) and a list of dependency pairs, determine a valid order in which all tasks can be completed.

Each dependency pair [a, b] means that task a depends on task b, so task b must be completed before task a can start.

If it's possible to complete all tasks, return any valid ordering. If a circular dependency exists that makes completion impossible, return an empty array.

Requirements

1. Return an array containing all task numbers in a valid completion order
2. Ensure all dependencies are satisfied in the returned ordering
3. If multiple valid orderings exist, return any one of them
4. Detect cycles and return an empty array if tasks cannot be completed
5. Handle edge cases like tasks with no dependencies

Constraints

• 1 ≤ numTasks ≤ 2000
• 0 ≤ dependencies.length ≤ 5000
• dependencies[i].length == 2
• 0 ≤ ai, bi < numTasks
• All dependency pairs are unique
• Time complexity should be O(V + E) where V is the number of tasks and E is the number of dependencies
• Space complexity should be O(V + E)

Examples

Example 1:

Input: numTasks = 4, dependencies = [[1,0],[2,1],[3,2]] Output: [0,1,2,3] Explanation: Task 0 has no dependencies and can be done first. Task 1 depends on 0, task 2 depends on 1, and task 3 depends on 2.

Example 2:

Input: numTasks = 4, dependencies = [[1,0],[2,0],[3,1],[3,2]] Output: [0,1,2,3] or [0,2,1,3] Explanation: Task 0 must be first. Tasks 1 and 2 both depend only on 0, so they can be done in either order. Task 3 depends on both 1 and 2, so it must be last.

Example 3:

Input: numTasks = 2, dependencies = [[1,0],[0,1]] Output: [] Explanation: Task 1 depends on task 0, and task 0 depends on task 1. This circular dependency makes completion impossible.