Course Schedule medium

Description

There are numCourses courses labeled 0 to numCourses - 1. You’re given a list prerequisites where prerequisites[i] = [a, b] means you must take course b before course a.

Return true if you can finish all courses, false otherwise.

Examples

> Case 1:
    Input:  numCourses = 2, prerequisites = [[1, 0]]
    Output: true       # Take 0, then take 1.
 
> Case 2:
    Input:  numCourses = 2, prerequisites = [[1, 0], [0, 1]]
    Output: false      # Cycle: 0 needs 1, 1 needs 0. Impossible.
 
> Case 3:
    Input:  numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
    Output: true       # 0 → 1 → 3 and 0 → 2 → 3. A valid order: 0,1,2,3.

Constraints

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000

Restating the problem

The prerequisites form a directed graph: edge b → a means “b must be taken before a.” The question becomes:

Does this directed graph have a cycle?

If yes → no valid ordering exists → return false. If no → it’s a DAG → a topological order exists → return true.

So this is cycle detection in a directed graph. Two classic approaches:

1. DFS with three-color marking. Track each node as unvisited / on-current-stack / fully-done. A back-edge to an “on-current-stack” node means a cycle.
2. BFS / Kahn’s algorithm. Repeatedly remove nodes with in-degree 0. If you can remove all n nodes, the graph is a DAG.

Both are O(V + E). Pick the one you find easier to write under pressure.

Approach 1: DFS with three colors

The three states for each node:

• 0 (white) — unvisited
• 1 (gray) — currently being visited (on the recursion stack)
• 2 (black) — fully visited (we’ve already explored everything reachable)

A cycle is found when DFS sees a gray node as a neighbour — that means we’ve looped back to something still on the call stack.

def can_finish(numCourses, prerequisites):
    adj = [[] for _ in range(numCourses)]
    for a, b in prerequisites:
        adj[b].append(a)      # b must come before a
 
    # 0 = unvisited, 1 = on stack, 2 = done
    color = [0] * numCourses
 
    def dfs(u):
        if color[u] == 1: return False     # found a cycle
        if color[u] == 2: return True      # already proven safe
        color[u] = 1
        for v in adj[u]:
            if not dfs(v): return False
        color[u] = 2
        return True
 
    for i in range(numCourses):
        if not dfs(i): return False
    return True

#include <vector>
using namespace std;
 
bool canFinish(int n, vector<vector<int>>& prereq) {
    vector<vector<int>> adj(n);
    for (auto& e : prereq) adj[e[1]].push_back(e[0]);
    vector<int> color(n, 0);
 
    function<bool(int)> dfs = [&](int u) -> bool {
        if (color[u] == 1) return false;
        if (color[u] == 2) return true;
        color[u] = 1;
        for (int v : adj[u]) {
            if (!dfs(v)) return false;
        }
        color[u] = 2;
        return true;
    };
 
    for (int i = 0; i < n; i++) {
        if (!dfs(i)) return false;
    }
    return true;
}

public boolean canFinish(int n, int[][] prereq) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : prereq) adj.get(e[1]).add(e[0]);
    int[] color = new int[n];
 
    for (int i = 0; i < n; i++) {
        if (!dfs(i, adj, color)) return false;
    }
    return true;
}
 
private boolean dfs(int u, List<List<Integer>> adj, int[] color) {
    if (color[u] == 1) return false;
    if (color[u] == 2) return true;
    color[u] = 1;
    for (int v : adj.get(u)) {
        if (!dfs(v, adj, color)) return false;
    }
    color[u] = 2;
    return true;
}

Approach 2: Kahn’s algorithm (BFS-based topological sort)

The idea: every DAG has at least one node with in-degree 0 — a node with no prerequisites. Remove it (and the edges going out of it), then look for another. Repeat until either the graph is empty (DAG, return true) or you’re stuck with nodes that still have prerequisites (cycle, return false).

from collections import deque
 
def can_finish(numCourses, prerequisites):
    in_degree = [0] * numCourses
    adj = [[] for _ in range(numCourses)]
    for a, b in prerequisites:
        adj[b].append(a)
        in_degree[a] += 1
 
    # Start with all zero-in-degree nodes
    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    processed = 0
    while queue:
        u = queue.popleft()
        processed += 1
        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
 
    return processed == numCourses

If we processed every course, all had a valid place in the ordering — no cycle. If some courses are stuck with positive in-degree, those form the cycle.

Comparison

Both are interview-correct answers; mention which you’d choose and why.

Analysis

• Time: O(V + E) for both.
• Space: O(V + E) for the adjacency list, plus O(V) for the visited / in-degree array.