Course Schedule IV

MEDIUM✓ CHIP-TIMEDLC #1462 — FULL STATEMENT ↗

The drill: Given direct course requirements, answer a batch of yes/no questions: for each pair, is the first course an ancestor requirement of the second — directly, or through some chain of other courses?

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A fixed number of courses comes with a list of direct prerequisite pairs, then a separate batch of queries, each asking about two specific courses. The task is to answer, for every query, whether the first course is a prerequisite of the second.

A prerequisite doesn't have to be direct — if course A requires B, and B requires C, then A counts as a prerequisite of C too, through that whole chain, no matter how many courses sit in between.

Every query is independent and judged against the same fixed set of requirements, so the underlying reachability between courses only needs to be worked out once and then reused for every question asked.

EX 01

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

→ [false, true]

ONE EDGE, BOTH DIRECTIONS ASKED

EX 02

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

→ [false, false]

NO REQUIREMENTS AT ALL

EX 03

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

→ [false, true, false, true]

A TWO-HOP CHAIN

up to a few hundred courses and a similar range of prerequisite pairs
queries can number in the thousands against the same course graph
prerequisite reaches through any length chain, not just direct pairs
each query answer is boolean — reachable through the chain, or not

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Direct requirements only tell you about immediate edges. A query can ask about two courses with no direct edge between them at all — what does "prerequisite" really mean once chains are involved?

HINT 2 THE STRUCTURE

A course is a prerequisite of another exactly when it can reach it by following requirement edges forward, any number of hops. That's a reachability question, and there are many queries against the same fixed graph.

HINT 3 ONE STEP FROM THE ANSWER

Compute full reachability once: for every pair (i, j), can i reach j at all? A triple loop that routes every pair through every possible middle course settles all of them together, then every query is a single lookup.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE REACH TABLEPATTERN · FLOYD–WARSHALL — TRANSITIVE CLOSURE3 courses · edges: 1→0, 2→1 · queries: (0,2) (2,0) (0,1) (1,0)

STEP 1

Seed the reach table directly from the prerequisite pairs: 1 reaches 0, 2 reaches 1. Everything else starts unknown.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/course-schedule-iv.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def checkIfPrerequisite(
        self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]
    ) -> List[bool]:
        reach = [[False] * numCourses for _ in range(numCourses)]
        for a, b in prerequisites:
            reach[a][b] = True

        for k in range(numCourses):
            for i in range(numCourses):
                if reach[i][k]:
                    for j in range(numCourses):
                        if reach[k][j]:
                            reach[i][j] = True

        return [reach[a][b] for a, b in queries]

TIME O(V³)SPACE O(V²)PYTHON · RACE PACE · 16 LN

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

        def reachable(src, dst):
            stack = [src]
            seen = {src}
            while stack:
                node = stack.pop()
                for nxt in graph[node]:
                    if nxt == dst:
                        return True
                    if nxt not in seen:
                        seen.add(nxt)
                        stack.append(nxt)
            return False

        return [reachable(a, b) for a, b in queries]

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

class Solution {
    public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        boolean[][] reach = new boolean[numCourses][numCourses];
        for (int[] p : prerequisites) reach[p[0]][p[1]] = true;

        for (int k = 0; k < numCourses; k++) {
            for (int i = 0; i < numCourses; i++) {
                if (!reach[i][k]) continue;
                for (int j = 0; j < numCourses; j++) {
                    if (reach[k][j]) reach[i][j] = true;
                }
            }
        }

        List<Boolean> out = new ArrayList<>();
        for (int[] q : queries) out.add(reach[q[0]][q[1]]);
        return out;
    }
}

TIME O(V³)SPACE O(V²)JAVA · RACE PACE · 19 LN

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

    public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
        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]);

        List<Boolean> out = new ArrayList<>();
        for (int[] q : queries) out.add(reachable(q[0], q[1]));
        return out;
    }

    private boolean reachable(int src, int dst) {
        Deque<Integer> stack = new ArrayDeque<>();
        Set<Integer> seen = new HashSet<>();
        stack.push(src);
        seen.add(src);
        while (!stack.isEmpty()) {
            int node = stack.pop();
            for (int nxt : graph.get(node)) {
                if (nxt == dst) return true;
                if (seen.add(nxt)) stack.push(nxt);
            }
        }
        return false;
    }
}

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

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