Course Schedule | Leetcode 207 | Kahn’s Algorithm Walk-through in Python

Check if you can finish every course when some need to be done first. We build the course graph, run Kahn’s BFS topological sort, and detect cycles. Step-by-step intuition, detailed code explanation, dry run, and Big-O analysis.

Here’s the [Problem Link] to begin with.

1. What does the problem ask?

You have numCourses labeled 0 … numCourses − 1.
Each pair [a, b] in prerequisites means:

Take course b before course a.

Return True if you can take all courses in some order.
Return False if the rules create a cycle that blocks progress.

2. Quick examples

Also check Detect Cycle in a Directed Graph – Kahn’s Algorithm

3. Intuition & Approach (trainer style)

3.1 Turning courses into a graph

• Think of every course as a node.
• A rule “b before a” is drawn as a directed edge from a to b in our code.
  Why this direction? We will remove a course after all arrows leaving it are handled (more on that soon).

3.2 What keeps us from finishing?

A cycle like 0 → 1 → 2 → 0.
Inside a cycle no course can be done first because each one waits for another in the loop.

3.3 Kahn’s algorithm in plain words

1. Indegree = number of incoming edges.
   For us: how many other courses still depend on this course.
2. Start queue with every course whose indegree is 0.
   Those courses have nobody waiting on them (in our edge direction) so we can safely “take” them now.
3. Process the queue until empty.
   • Pop a course, mark it as finished.
   • For every arrow that leaves it, lower the neighbour’s indegree.
   • If a neighbour’s indegree drops to 0, it is now free to take → push it into the queue.
4. After BFS ends:
   • If we finished all courses → no cycle → return True.
   • If some courses were never freed (queue never reached them) → cycle exists → return False.

3.4 Why it works

Removing zero-indegree nodes layer by layer mimics deleting arrows.
If a cycle exists, its nodes can never reach indegree 0, so they never enter the queue.
The size of the “finished” list therefore tells us instantly whether a cycle was present.

4. Code

from collections import deque


class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # Build adjacency list and indegree array
        adj_list = [[] for _ in range(numCourses)]
        indegrees = [0 for _ in range(numCourses)]

        for u, v in prerequisites:  # edge: u depends on v
            adj_list[u].append(v)   # arrow u → v
            indegrees[v] += 1       # v has one more incoming edge

        # Collect all starting courses (indegree 0)
        queue = deque()
        result = []                 # keeps the order we "finish" courses
        for i in range(numCourses):
            if indegrees[i] == 0:
                queue.append(i)

        # Kahn's BFS
        while len(queue) != 0:
            current_node = queue.popleft()  # course ready to finish
            result.append(current_node)
            for adjNode in adj_list[current_node]:  # courses it points to
                indegrees[adjNode] -= 1             # remove the edge
                if indegrees[adjNode] == 0:         # neighbour now free
                    queue.append(adjNode)

        # If we finished every course, schedule is possible
        if len(result) == numCourses:
            return True
        return False

5. Step-by-step code explanation

1. Lines 5–8 – We create two helpers:
   • adj_list[u] → list of courses that u points to (its prerequisites in our chosen direction).
   • indegrees[v] → how many arrows point into course v.
2. Lines 10–12 – For every rule [u, v] we:
   • Add v into u’s list.
   • Increment v’s indegree.
   • Now v “waits” for one more course before it can be freed.
3. Lines 15–18 – Fill the queue with all courses whose indegree is zero:
   They are the ones that no other course depends on, so we finish them first.
4. Lines 21–27 – Main BFS loop:
   • Pop a course current_node and append it to result (meaning we completed it).
   • Visit every neighbour adjNode.
   • Decrease that neighbour’s indegree because one dependency disappeared.
   • As soon as a neighbour’s indegree becomes 0, push it to the queue—
     it is now free to complete in a later round.
5. Lines 29–32 – After the queue empties:
   • If we completed numCourses courses, no cycle existed → return True.
   • Otherwise at least one course was stuck in a cycle → return False.

6. Dry run on a tricky case

numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]

So here the algorithm shows a cycle, which is correct because 0 ↔ (1 and 2) forms a deadlock.

7. Complexity

V = numCourses, E = len(prerequisites).

8. Conclusion

By viewing courses and prerequisites as a graph and repeatedly removing nodes with zero indegree (Kahn’s BFS topological sort), we can:

• Detect cycles (impossible schedules) quickly.
• Build a valid course order when possible (just read the result list).

This approach is linear, easy to code, and mirrors how real-world scheduling systems handle dependencies.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.