There are numCourses courses labelled 0 to numCourses - 1. Each pair prerequisites[i] = [a, b] means you must finish course b before course a. Return true if it is possible to finish every course, otherwise false.
- 1 <= numCourses <= 2000
- 0 <= prerequisites.length <= 5000
- prerequisites[i] = [a, b] with 0 <= a, b < numCourses
- All pairs are distinct
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Trying every order of courses is factorial. As a graph, each prerequisite is an edge b -> a, and we can finish everything only if there is no directed cycle. Kahn's algorithm (BFS topological sort) checks this: count each course's incoming edges (in-degree); courses with in-degree 0 can be taken now. Taking a course removes its outgoing edges, which may free more courses. If every course gets taken, the graph is acyclic; courses stuck in a cycle never reach in-degree 0.
Algorithm
- Build an adjacency list
b -> aand an in-degree array. - Push every course with in-degree 0 into a queue.
- Pop a course, count it as taken, and decrease the in-degree of each course it unlocks.
- Push any course whose in-degree drops to 0.
- Return
trueif the number taken equalsnumCourses.
O(V + E)Space: O(V + E)class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: graph = [[] for _ in range(numCourses)] indeg = [0] * numCourses for a, b in prerequisites: graph[b].append(a) # b -> a indeg[a] += 1 queue = deque(i for i in range(numCourses) if indeg[i] == 0) taken = 0 while queue: course = queue.popleft() taken += 1 for nxt in graph[course]: indeg[nxt] -= 1 if indeg[nxt] == 0: # all its prerequisites are done queue.append(nxt) return taken == numCourses