Practice/Amazon/Leetcode 207. Course Schedule

Leetcode 207. Course Schedule

CodingMust

Problem

You are managing a software project with multiple modules that have dependencies on each other. Each module is numbered from 0 to numProjects - 1. Some modules cannot be built until their prerequisite modules are built first.

You are given:

• numProjects: the total number of modules in the project
• dependencies: an array of dependency pairs where [a, b] means module a depends on module b (module b must be built before module a)

Determine whether it is possible to build all modules. Return true if a valid build order exists, or false if circular dependencies prevent completion.

Requirements

1. Analyze the dependency structure to detect cycles
2. Return true if all modules can be built (no cycles exist)
3. Return false if circular dependencies make it impossible to complete all modules
4. Handle edge cases including no dependencies and self-referencing cycles

Constraints

• 1 <= numProjects <= 2000
• 0 <= dependencies.length <= 5000
• dependencies[i].length == 2
• 0 <= ai, bi < numProjects
• All dependency pairs are unique

Examples

Example 1:

Input: numProjects = 4, dependencies = [[1,0],[2,0],[3,1],[3,2]] Output: true Explanation: One valid build order is: 0 → 1 → 2 → 3 Module 0 has no dependencies, so build it first. Modules 1 and 2 both depend only on 0, so build them next. Module 3 depends on both 1 and 2, so build it last.

Example 2:

Input: numProjects = 2, dependencies = [[1,0],[0,1]] Output: false Explanation: Module 1 depends on module 0, and module 0 depends on module 1. This circular dependency makes it impossible to build either module.

Example 3:

Input: numProjects = 3, dependencies = [] Output: true Explanation: With no dependencies, all modules can be built in any order.