DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Course Schedule II

mediumGraphs Must-do

Problem statement

There are numCourses courses labelled 0 to numCourses - 1. Each entry [a, b] in prerequisites means course b must be finished before you can start course a.

Return an order in which you can take every course. If several orders work, return any of them. If the prerequisites contain a cycle so that no order works, return an empty array.

Examples

Example 1

Input: numCourses = 3, prerequisites = [[2, 0], [2, 1], [1, 0]]

Output: [0, 1, 2]

Explanation: Course 0 has no prerequisites. Course 1 needs 0. Course 2 needs both 0 and 1, so it goes last. This is the only valid order.

Example 2

Input: numCourses = 3, prerequisites = [[0, 1], [1, 2], [2, 0]]

Output: []

Explanation: 0 needs 1, 1 needs 2, and 2 needs 0. None of them can ever go first.

Hints

Approach

Kahn's algorithm. Instead of rescanning to find ready courses, keep them in a queue and update counts as courses finish.

  1. Build graph[b], the courses that list b as a prerequisite, and indegree[a], the number of prerequisites a still waits on.
  2. Push every course with indegree == 0 onto a queue.
  3. Pop a course and append it to the order. For each course that depends on it, subtract one from its in-degree. When that reaches zero, push it.
  4. If the order ends up with fewer than numCourses entries, the leftovers are on or behind a cycle: return [].

Every course is queued once and every edge is relaxed once, so it is linear. The "fewer than numCourses" check is the cycle detector; there is no separate pass.

ComplexityTime O(V + E)Space O(V + E)
Python
from collections import deque
class Solution:
def findOrder(self, numCourses: int, prerequisites: list[list[int]]) -> list[int]:
graph = [[] for _ in range(numCourses)]
indegree = [0] * numCourses
for course, pre in prerequisites:
graph[pre].append(course)
indegree[course] += 1
queue = deque(c for c in range(numCourses) if indegree[c] == 0)
order = []
while queue:
c = queue.popleft()
order.append(c)
for nxt in graph[c]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
return order if len(order) == numCourses else []

Follow-up questions

  • Courses in the same round have no dependency between them and can be taken in parallel. Return the minimum number of rounds. (Process the queue level by level.)
  • When a cycle exists, report which courses are part of it.

Frequently asked questions

Yes. Run a DFS that colours nodes white (unvisited), grey (on the current path) and black (finished). Meeting a grey node means a cycle. Append each node when it turns black; the reverse of that list is a valid order. It is also O(V + E), but it recurses, so very deep chains can hit the recursion limit in Python.

Any tool that has to start, build or apply things in dependency order is doing a topological sort: Terraform ordering resource creation, systemd ordering units with After=, a CI pipeline running jobs with needs:, or a package manager resolving install order. A cycle is exactly the "dependency cycle" error those tools report.