Understanding the Problem
You are given an integer numCourses
, which represents the total number of courses labeled from 0
to numCourses - 1
. You are also given a list of prerequisite pairs prerequisites
, where each pair [a, b]
means that you must complete course b
before course a
.
Your goal is to determine a valid order to take all the courses, such that the prerequisites are respected. If there’s no way to complete all courses due to circular dependencies (cycles), you should return an empty array.
Step-by-Step Solution with Example
Step 1: Represent the problem as a directed graph
Each course is a node. Each prerequisite pair [a, b]
becomes a directed edge from b → a
. This means course b
must come before a
.
Step 2: Build the adjacency list and indegree array
The adjacency list keeps track of all courses that depend on a course. The indegree array counts how many prerequisites each course has.
Input:
numCourses = 4,
prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
Adjacency List:
0 → [1, 2]
1 → [3]
2 → [3]
Indegree:
[0, 1, 1, 2]
Step 3: Initialize the queue with courses that have zero prerequisites
We can start with courses that have indegree 0
because they don’t depend on any other course.
In this example, course 0
has no prerequisites, so we begin with queue = [0]
.
Step 4: Perform topological sort using Kahn’s Algorithm
We repeat the following:
- Pop a course from the queue
- Add it to the result list
- Reduce the indegree of all its neighbors
- If any neighbor’s indegree becomes 0, add it to the queue
Process:
queue = [0] → result = []
take 0 → result = [0]
decrease indegree of 1 → indegree[1] = 0 → add 1 to queue
decrease indegree of 2 → indegree[2] = 0 → add 2 to queue
queue = [1, 2]
take 1 → result = [0, 1]
decrease indegree of 3 → indegree[3] = 1
take 2 → result = [0, 1, 2]
decrease indegree of 3 → indegree[3] = 0 → add 3 to queue
take 3 → result = [0, 1, 2, 3]
Step 5: Verify result length
If the result contains all numCourses
(i.e., length equals numCourses
), we have found a valid order. If not, it means there was a cycle.
Edge Cases
- No prerequisites: If the list is empty, all courses can be taken in any order. For example,
numCourses = 3, prerequisites = []
→ possible result: [0, 1, 2]
.
- Cycle in prerequisites: Example
[[1, 0], [0, 1]]
forms a cycle. No course order is valid. Return []
.
- Disconnected components: Example
[[1, 0], [3, 2]]
. These are independent chains and can be solved separately. Valid result: [0, 1, 2, 3]
or [2, 3, 0, 1]
.
Finally
This problem is a classic example of topological sorting in a directed graph. Kahn’s Algorithm is an efficient way to build the course order using a queue and indegree tracking. Always ensure to handle cycles and special cases like no prerequisites or disconnected graphs.
Practicing this problem strengthens your understanding of graph algorithms and helps you apply them in scheduling and dependency resolution scenarios.
Comments
Loading comments...