Coding interview problems › Graphs & Grids

🗺️ Graphs & Grids Medium

Course Schedule

Course Schedule explained: prerequisites as a directed graph, and Kahn's topological sort to detect a cycle. Tested Python code, pitfalls and a live visual.

Also searched as: detect a cycle in a directed graph · can all courses be finished with prerequisites · Kahn's algorithm cycle detection

🗂️

Try it live Free

Topological Sort

In the Topological Sort lab, watch Kahn's algorithm peel unblocked courses off the dependency graph, then add a cycle and see it get stuck.

Open the playground →

The problem

There are n courses labelled 0 to n-1 and a list of pairs [a, b] meaning you must take course b before course a. Return whether it is possible to finish every course.

Inputn = 2, prerequisites = [[1, 0]]
OutputTrue

Take 0, then 1.

Inputn = 2, prerequisites = [[1, 0], [0, 1]]
OutputFalse

Each needs the other first: a cycle.

The key insight

Draw an arrow from each prerequisite to the course that needs it. You can finish everything exactly when this directed graph has no cycle. Kahn's algorithm finds out by repeatedly taking a course with no remaining prerequisites (in-degree 0) and removing its arrows. If you manage to take all n courses, there was no cycle.

Brute force first: Trying every ordering of the courses and checking it is O(n!) and hopeless beyond tiny inputs.

Step-by-step approach

  1. Build an adjacency list b -> a and count each course's in-degree (number of prerequisites).
  2. Push every course with in-degree 0 onto a queue.
  3. Pop a course, count it as taken, and decrement the in-degree of every course that depends on it.
  4. Whenever a course's in-degree drops to 0, push it.
  5. Return whether the number of taken courses equals n.

Python solution

PYTHON 3tested
from collections import deque


def can_finish(num_courses, prerequisites):
    graph = [[] for _ in range(num_courses)]
    indeg = [0] * num_courses
    for course, pre in prerequisites:
        graph[pre].append(course)      # pre must come before course
        indeg[course] += 1
    q = deque(c for c in range(num_courses) if indeg[c] == 0)
    taken = 0
    while q:
        c = q.popleft()
        taken += 1
        for nxt in graph[c]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                q.append(nxt)
    return taken == num_courses        # leftovers sit on a cycle

Complexity

TimeO(V + E)
SpaceO(V + E)

Each course is pushed and popped once (V) and each prerequisite edge is relaxed once (E). The adjacency list stores all edges.

Common mistakes

Frequently asked questions

What is the time and space complexity of Course Schedule?

O(V + E) time and space, where V is the number of courses and E the number of prerequisite pairs, for both Kahn's BFS and the DFS three-colour method.

Can I solve it with DFS instead of Kahn's algorithm?

Yes. Colour each node white, grey (on the current path) or black (finished). Meeting a grey node during DFS means a back edge, which is a cycle.

What about self-loops like [1, 1]?

A course that requires itself gives it in-degree that can never drop to 0, so Kahn's algorithm correctly reports it is impossible.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Graphs & Grids Graph Search: BFS vs DFS lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.