Course Schedule

Problem

There are a total of numCourses courses you have to take. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai. Return true if you can finish all courses, or false otherwise.

Examples

The brute-force approach

For each course, DFS from it following prerequisite chains. If you ever revisit a course already in the current DFS path, there's a cycle.

def hasCycle(course, visited, inPath):
    if inPath[course]: return True   # cycle
    if visited[course]: return False # already cleared
    inPath[course] = True
    for prereq in adj[course]:
        if hasCycle(prereq, visited, inPath):
            return True
    inPath[course] = False
    visited[course] = True
    return False

O(V + E) per DFS call, called for each node. With memoization (marking fully-explored nodes) it becomes O(V + E) total, which is already optimal. The cleaner framing is Kahn's algorithm (BFS topological sort), which detects cycles by checking if all nodes are processed.

Spotting the pattern

This is a Topological Sort problem. The key question to ask yourself:

If a course has zero prerequisites, you can take it immediately. After taking it, what happens to the courses that depended on it?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.