Course Schedule IV

NeetCode: Course Schedule IV · LeetCode: 1462. Course Schedule IV · Difficulty: Medium

There are numCourses courses labelled 0 to numCourses - 1. Each pair [a, b] in prerequisites means you must take a before b. Prerequisites are transitive: if a is a prerequisite of b and b of c, then a is a prerequisite of c. For each query [u, v], answer whether u is a (direct or indirect) prerequisite of v. The graph has no cycles.

Example

Text

Input:  numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
Output: [false, true]

Input:  numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
Output: [true, true]

Input:  numCourses = 3, prerequisites = [], queries = [[1,0],[1,2]]
Output: [false, false]

Brute force: a DFS for every query

Build an adjacency list a -> b. To answer [u, v], run a DFS from u and report whether v is reachable. Each query re-explores the graph from scratch, even though many queries share the same source. The adjacency list is a List<List<Integer>>.

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class Solution {
        private boolean dfs(List<List<Integer>> graph, int node, int target, boolean[] seen) {
            if (node == target) {
                return true;
            }
            seen[node] = true;
            for (int next : graph.get(node)) {
                if (!seen[next] && dfs(graph, next, target, seen)) {
                    return true;
                }
            }
            return false;
        }

        public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
            List<List<Integer>> 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> answer = new ArrayList<>();
            for (int[] q : queries) {
                answer.add(dfs(graph, q[0], q[1], new boolean[numCourses]));
            }
            return answer;
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.checkIfPrerequisite(2, new int[][]{{1, 0}}, new int[][]{{0, 1}, {1, 0}}));
        int[][] pre = {{1, 2}, {1, 0}, {2, 0}};
        System.out.println(s.checkIfPrerequisite(3, pre, new int[][]{{1, 0}, {1, 2}}));
        System.out.println(s.checkIfPrerequisite(3, new int[][]{}, new int[][]{{1, 0}, {1, 2}}));
    }
}

Output

[false, true]
[true, true]
[false, false]

With V courses, E prerequisites and Q queries, each query costs O(V + E). Time: O(Q * (V + E)) plus O(V + E) to build the graph. Space: O(V + E).

Optimal: transitive closure (Floyd-Warshall style)

Since all queries are about reachability, compute the answer for every pair once. Let reach[i][j] be true if i is a prerequisite of j. Start with the direct edges, then for each intermediate course k, set reach[i][j] = true whenever reach[i][k] and reach[k][j]. k must be the outermost loop: after processing k, every path whose intermediate courses are all in 0 to k is recorded. The result is a List<Boolean>, and answer.add(boolean) boxes each value to Boolean. Each query is then an O(1) lookup.

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class Solution {
        public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
            int n = numCourses;
            boolean[][] reach = new boolean[n][n];
            for (int[] p : prerequisites) {
                reach[p[0]][p[1]] = true;
            }
            for (int k = 0; k < n; k++) {
                for (int i = 0; i < n; i++) {
                    if (!reach[i][k]) {
                        continue;
                    }
                    for (int j = 0; j < n; j++) {
                        if (reach[k][j]) {
                            reach[i][j] = true;
                        }
                    }
                }
            }
            List<Boolean> answer = new ArrayList<>();
            for (int[] q : queries) {
                answer.add(reach[q[0]][q[1]]);
            }
            return answer;
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.checkIfPrerequisite(2, new int[][]{{1, 0}}, new int[][]{{0, 1}, {1, 0}}));
        int[][] pre = {{1, 2}, {1, 0}, {2, 0}};
        System.out.println(s.checkIfPrerequisite(3, pre, new int[][]{{1, 0}, {1, 2}}));
        System.out.println(s.checkIfPrerequisite(3, new int[][]{}, new int[][]{{1, 0}, {1, 2}}));
    }
}

Output

[false, true]
[true, true]
[false, false]

The closure costs O(V^3) once and each query is then a lookup. It pays off when Q is large compared with V^2; for few queries on a large sparse graph the per-query DFS can be cheaper. Running a DFS or BFS from every node, or keeping a bitset of ancestors per node in topological order, are alternatives. Time: O(V^3 + E + Q). Space: O(V^2).