Sign in
Skip to solution
mediumDSA

How do you solve the course schedule (prerequisites) problem?

1.1k views
01

Understand the problem

Explain detecting a valid ordering.

graphstopological-sort
02

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

Model courses as a directed graph of prerequisites; a valid schedule exists iff there's no cycle. Use Kahn's algorithm (repeatedly remove zero in-degree nodes) — if you can't remove all of them, there's a cycle. O(V+E).

Solution ready — 2 min read

Classified // press E to declassify

04

Read the code

Kahn's algorithm (BFS topo-sort)
Run Playground
from collections import deque

def can_finish(num_courses, prerequisites):
    graph = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses
    for course, pre in prerequisites:
        graph[pre].append(course)
        indegree[course] += 1
    q = deque(c for c in range(num_courses) if indegree[c] == 0)
    taken = 0
    while q:
        c = q.popleft()
        taken += 1
        for nxt in graph[c]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                q.append(nxt)
    return taken == num_courses


# --- demo ---
print(can_finish(2, [[1, 0]]))            # True   (take 0, then 1)
print(can_finish(2, [[1, 0], [0, 1]]))    # False  (0 and 1 depend on each other)
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

No responses yet. Be the first to share what you think.

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 33 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track