Course Schedule (Topological Sort)

Table of Contents +

This one sounds like a school problem. But it is really a graph problem. The interviewer hands you courses and some “do this before that” rules. They want to see if you notice the hidden problem: a cycle. A cycle is when the rules loop back on themselves. Like course A needs B, B needs C, and C needs A. If that happens, you can never start, so you can never finish.

📚 The Problem

You are given a number of courses, labeled 0 to n - 1. You are also given a list of prerequisite pairs. A pair [a, b] means: to take course a, you must finish course b first. Your job is to return true if you can finish all the courses, and false if you cannot.

Here is what that looks like:

Input:  numCourses = 4, prerequisites = [[1, 0], [2, 1], [3, 2]]
Output: true   (take them in order 0, 1, 2, 3)


Input:  numCourses = 2, prerequisites = [[1, 0], [0, 1]]
Output: false  (0 needs 1 and 1 needs 0, so they block each other forever)

So really you are being asked one thing. Does this set of rules have a cycle? No cycle means you can finish. A cycle means you are stuck.

🧠 Think of It as a Graph First

Before any code, let’s picture the rules. Each course is a dot. Each pair [a, b] is an arrow that goes from b to a. It means “do b, then you can do a”. When you draw all the arrows, you get a directed graph. A directed graph is just dots joined by one-way arrows.

Now the simple-but-messy idea would be to try every possible order of courses and check if any order works. But the number of orders grows very fast. With even a handful of courses that becomes far too slow. So we need a smarter way that walks the graph just once.

🔢 The In-Degree Idea (Kahn’s Method)

Here is the clean trick. For each course, count how many arrows point into it. That count is called the in-degree. The in-degree tells you how many prerequisites a course still has waiting.

Think about it like a real semester. A course with in-degree 0 has no prerequisites left. So you can take it right now. Once you finish it, you can cross it off as a prerequisite for the courses that depended on it. That lowers their in-degree by one. Some of them might now drop to 0. That means they are ready too.

So here is the plan. Keep taking every course whose in-degree is 0, and keep lowering the counts. If you manage to take all the courses this way, there was no cycle, so the answer is true. If at some point no course has in-degree 0 but courses still remain, then those leftover courses are tangled in a cycle, so the answer is false. This whole approach has a name: Kahn’s algorithm.

Steps to solve with Kahn’s topological sort

Let’s write the steps down before any code.

  1. Build the graph. For each pair [a, b], add a to the neighbor list of b, and add 1 to the in-degree of a.
  2. Put every course with in-degree 0 into a queue. These have no prerequisites left.
  3. Keep a counter taken = 0.
  4. While the queue is not empty:
    • Remove a course from the front. Add 1 to taken.
    • For each neighbor of that course, lower its in-degree by 1. If a neighbor’s in-degree becomes 0, push it into the queue.
  5. At the end, if taken equals numCourses, return true. Otherwise return false.

Why the counter is enough

You do not even need to store the final order to answer this question. You only need to know if every course got taken. So a simple counter does the job. If it falls short of numCourses, the courses that never made it must be locked in a cycle.

Code for Course Schedule

Now let’s see it in every language.

course_schedule.py
from collections import deque


# can we finish all courses? (no cycle in prerequisites)
def can_finish(num_courses, prerequisites):
    graph = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses


    # pair [a, b] means do b before a
    for a, b in prerequisites:
        graph[b].append(a)   # b points to a
        indegree[a] += 1     # a gains one prerequisite


    # start with courses that have no prerequisites
    queue = deque(i for i in range(num_courses) if indegree[i] == 0)


    taken = 0
    while queue:
        course = queue.popleft()
        taken += 1
        for nxt in graph[course]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                queue.append(nxt)


    return taken == num_courses


def main():
    prereq1 = [[1, 0], [2, 1], [3, 2]]
    prereq2 = [[1, 0], [0, 1]]
    print("Can finish (no cycle):", can_finish(4, prereq1))
    print("Can finish (cycle):", can_finish(2, prereq2))


if __name__ == "__main__":
    main()

The output of the above code will be:

Can finish (no cycle): True
Can finish (cycle): False

⏱️ Time and Space Complexity

Here V is the number of courses and E is the number of prerequisite pairs.

Approach Time Space
Try every order (brute force) O(V!) O(V)
Kahn’s topological sort O(V + E) O(V + E)

Kahn’s method touches each course once and each arrow once. So the time is O(V + E). That is as fast as you can get for this. The space is O(V + E) because you store the graph plus the in-degree counts and the queue. The brute force way is far worse, since trying every order grows like a factorial.

The other way to spot a cycle

Kahn’s method (BFS with in-degrees) is the clean answer here. But you can also solve this with DFS by marking nodes as “being visited” and catching when you reach a node that is already on the current path. Both are O(V + E). Pick the one you can explain calmly. Most people find the in-degree queue easier to talk through.

🧩 Key Takeaways

  • ✅ “Can you finish all courses?” is really asking “does the prerequisite graph have a cycle?”
  • ✅ Build a directed graph where each pair [a, b] adds an arrow from b to a and bumps the in-degree of a.
  • ✅ Kahn’s method starts from courses with in-degree 0, then lowers counts as it processes the queue.
  • ✅ If the number of taken courses equals numCourses, there is no cycle, so return true.
  • ✅ Time is O(V + E) and space is O(V + E).

Check Your Knowledge

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    In this problem, what does it really mean if you 'cannot finish all courses'?

    Why: If the rules loop back on each other (a cycle), no course in that loop can ever start, so you can never finish all of them.

  2. 2

    What does the in-degree of a course tell you?

    Why: In-degree counts the arrows pointing into a course, which is the number of prerequisites it still needs before you can take it.

  3. 3

    Which courses go into the queue at the very start of Kahn's method?

    Why: Courses with in-degree 0 have no prerequisites left, so they are ready to take immediately and seed the queue.

  4. 4

    What is the time complexity of Kahn's topological sort here?

    Why: Each course (vertex) and each prerequisite (edge) is processed exactly once, giving O(V + E).

Score: 0 / 4

🚀 What’s Next?

Now that you can spot a cycle with in-degrees, build on it with these:

Course Schedule is the classic way interviewers test if you can see a graph hiding inside a word problem. Once the in-degree pattern clicks, a lot of dependency questions start to look the same.

Previous Clone a Graph Next Climbing Stairs

Share & Connect

Share on LinkedIn