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.

Stuck? AI Nudge Available

Get a conceptual hint to guide your logic without spoiling the final implementation.

03

Study the solution

The solution is waiting

Give it an honest attempt first — then compare your thinking with the full walkthrough.

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.