Course Schedule

MEDIUM✓ CHIP-TIMEDLC #207 — FULL STATEMENT ↗

The drill: Some courses require other courses first. Given every such requirement, decide whether it is possible to take all the courses at all — or whether the requirements loop back on themselves and nothing can ever be scheduled.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

There are a fixed number of courses, numbered from 0 upward, and a list of prerequisite pairs where one course must be completed before another. The task is to decide whether every course could ever be finished at all under those rules.

Finishing becomes impossible exactly when some group of courses ends up needing each other in a loop — course A needs B, which eventually needs A again, so neither one can ever go first.

The answer is a simple true or false: true if some valid order exists to take every course, false if the requirements tangle into a cycle that blocks all of them.

EX 01

numCourses = 2 · prerequisites = [[1, 0]]

→ true

ONE REQUIREMENT, NO LOOP

EX 02

numCourses = 2 · prerequisites = [[1, 0], [0, 1]]

→ false

THE TWO COURSES NEED EACH OTHER

EX 03

numCourses = 1 · prerequisites = []

→ true

A SINGLE COURSE, NOTHING TO REQUIRE

up to a few thousand courses and prerequisite pairs
a prerequisite pair never lists a course as its own requirement directly
duplicate prerequisite pairs may appear and shouldn't change the answer
answer is boolean — whether any valid completion order exists at all

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

A requirement is a directed edge: to take course A you first need course B. The whole schedule is impossible exactly when some group of courses needs each other in a loop. What structure in a directed graph is that loop?

HINT 2 THE STRUCTURE

The question is really: does this directed graph contain a cycle? Detecting one needs to track not just visited nodes, but nodes currently on the path being explored.

HINT 3 ONE STEP FROM THE ANSWER

Peel off courses with zero remaining requirements one at a time, removing their edges as you go. If every course eventually gets peeled, there was no cycle — if some are stuck forever needing each other, there was.

COACH'S BOARD — THE PATTERN, STEP BY STEP

PEELING THE PREREQUISITESPATTERN · TOPOLOGICAL SORT — KAHN4 courses · edges: 0→1, 0→2, 1→3, 2→3

QUEUE

— empty —

STEP 1

Count arrows pointing INTO each course — its unfinished prerequisites.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/course-schedule.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = [[] for _ in range(numCourses)]
        indeg = [0] * numCourses
        for a, b in prerequisites:
            graph[b].append(a)  # taking b unlocks a
            indeg[a] += 1

        queue = collections.deque(c for c in range(numCourses) if indeg[c] == 0)
        taken = 0
        while queue:
            course = queue.popleft()
            taken += 1
            for nxt in graph[course]:
                indeg[nxt] -= 1
                if indeg[nxt] == 0:
                    queue.append(nxt)

        return taken == numCourses

TIME O(V+E)SPACE O(V+E)PYTHON · RACE PACE · 19 LN

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = [[] for _ in range(numCourses)]
        for a, b in prerequisites:
            graph[a].append(b)  # a requires b

        def has_cycle(course, on_path):
            if course in on_path:
                return True
            on_path.add(course)
            for pre in graph[course]:
                if has_cycle(pre, on_path):
                    return True
            on_path.remove(course)  # no permanent "cleared" mark — siblings re-walk this subtree
            return False

        for c in range(numCourses):
            if has_cycle(c, set()):
                return False
        return True

TIME O(V·(V+E))SPACE O(V+E)PYTHON · TRAINING PACE · 20 LN

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
        int[] indeg = new int[numCourses];
        for (int[] p : prerequisites) {
            graph.get(p[1]).add(p[0]);
            indeg[p[0]]++;
        }

        Deque<Integer> queue = new ArrayDeque<>();
        for (int c = 0; c < numCourses; c++) if (indeg[c] == 0) queue.add(c);

        int taken = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            taken++;
            for (int nxt : graph.get(course)) {
                if (--indeg[nxt] == 0) queue.add(nxt);
            }
        }
        return taken == numCourses;
    }
}

TIME O(V+E)SPACE O(V+E)JAVA · RACE PACE · 24 LN

class Solution {
    private List<List<Integer>> graph;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());
        for (int[] p : prerequisites) graph.get(p[0]).add(p[1]);

        for (int c = 0; c < numCourses; c++) {
            if (hasCycle(c, new HashSet<>())) return false;
        }
        return true;
    }

    private boolean hasCycle(int course, Set<Integer> onPath) {
        if (onPath.contains(course)) return true;
        onPath.add(course);
        for (int pre : graph.get(course)) {
            if (hasCycle(pre, onPath)) return true;
        }
        onPath.remove(course); // no permanent "cleared" mark — siblings re-walk this subtree
        return false;
    }
}

TIME O(V·(V+E))SPACE O(V+E)JAVA · TRAINING PACE · 24 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED