Course Schedule

Problem Description

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a, b] indicates that you must take course b first if you want to take course a.

For example, the pair [0, 1] indicates that to take course 0 you must first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Examples

Constraints

• 1 ≤ numCourses ≤ 2000
• 0 ≤ prerequisites.length ≤ 5000
• prerequisites[i].length == 2
• 0 ≤ a, b < numCourses
• All the pairs prerequisites[i] are unique.

Detecting Deadlocks in Dependency Chains

We can model the courses as vertices and prerequisites as directed edges in a graph. For example, if course b is a prerequisite for a, we add a directed edge b -> a.

Taking all courses is possible only if there are no deadlocks in the dependency chains. A deadlock corresponds to a cycle in the directed graph. For example, if course 0 requires 1, and 1 requires 0, we have a cycle, and neither course can be started.

Finding if we can complete all courses is equivalent to checking if the graph is a Directed Acyclic Graph (DAG). We can do this using DFS cycle detection, or Kahn’s algorithm (BFS topological sort using in-degrees).

Solution 1: DFS Cycle Detection

Use a visited array to track node states during traversal: 0 for unvisited, 1 for visiting (on the current path), and 2 for visited (confirmed safe). If we attempt to visit a node marked 1, we have detected a cycle.

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

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // build adjacency list
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] pre : prerequisites) {
            adj.get(pre[1]).add(pre[0]);
        }

        int[] visited = new int[numCourses]; // 0=unvisited, 1=visiting, 2=visited

        for (int i = 0; i < numCourses; i++) {
            if (visited[i] == 0) {
                if (hasCycle(i, adj, visited)) return false;
            }
        }
        return true;
    }

    private boolean hasCycle(int node, List<List<Integer>> adj, int[] visited) {
        visited[node] = 1; // mark as visiting

        for (int neighbor : adj.get(node)) {
            if (visited[neighbor] == 1) return true; // cycle detected
            if (visited[neighbor] == 0) {
                if (hasCycle(neighbor, adj, visited)) return true;
            }
        }

        visited[node] = 2; // mark as visited (safe)
        return false;
    }
}

class Solution:
    def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
        # build adjacency list
        adj = {i: [] for i in range(numCourses)}
        for course, pre in prerequisites:
            adj[pre].append(course)

        visited = [0] * numCourses  # 0=unvisited, 1=visiting, 2=visited

        def has_cycle(node):
            visited[node] = 1  # mark as visiting

            for neighbor in adj[node]:
                if visited[neighbor] == 1:
                    return True  # cycle detected
                if visited[neighbor] == 0:
                    if has_cycle(neighbor):
                        return True

            visited[node] = 2  # mark as visited (safe)
            return False

        for i in range(numCourses):
            if visited[i] == 0:
                if has_cycle(i):
                    return False

        return True

#include <vector>

class Solution {
private:
    bool hasCycle(int node, const std::vector<std::vector<int>>& adj, std::vector<int>& visited) {
        visited[node] = 1; // mark as visiting

        for (int neighbor : adj[node]) {
            if (visited[neighbor] == 1) return true; // cycle detected
            if (visited[neighbor] == 0) {
                if (hasCycle(neighbor, adj, visited)) return true;
            }
        }

        visited[node] = 2; // mark as visited (safe)
        return false;
    }

public:
    bool canFinish(int numCourses, std::vector<std::vector<int>>& prerequisites) {
        std::vector<std::vector<int>> adj(numCourses);
        for (const auto& pre : prerequisites) {
            adj[pre[1]].push_back(pre[0]);
        }

        std::vector<int> visited(numCourses, 0); // 0=unvisited, 1=visiting, 2=visited

        for (int i = 0; i < numCourses; i++) {
            if (visited[i] == 0) {
                if (hasCycle(i, adj, visited)) return false;
            }
        }
        return true;
    }
};

Complexity Analysis:

• Time Complexity: O(V + E) where V is the number of courses (vertices) and E is the number of prerequisites (edges). We visit each course and traverse each dependency once.
• Space Complexity: O(V + E) representing the graph adjacency list and the recursive call stack depth.

Where it breaks: If there are no prerequisites (prerequisites is empty), the cycles check returns true immediately, which is correct. If numCourses is larger than the stack limit, recursion can crash, which is not an issue with the limit of 2000.

Solution 2: Kahn’s Algorithm (BFS Topological Sort)

Track the in-degree (number of incoming prerequisite edges) of every course. Courses with in-degree 0 have no prerequisites and can be taken immediately. Push them into a queue.

Pop courses from the queue, decrement the in-degree of their neighbors, and push neighbors that hit in-degree 0. Track the count of popped courses. If this count equals numCourses, we have successfully sorted the DAG.

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adj = new ArrayList<>();
        int[] inDegree = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }

        // compute in-degrees and build adjacency list
        for (int[] pre : prerequisites) {
            adj.get(pre[1]).add(pre[0]);
            inDegree[pre[0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) queue.offer(i);
        }

        int count = 0;
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            count++;

            for (int neighbor : adj.get(curr)) {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }

        return count == numCourses;
    }
}

from collections import deque


class Solution:
    def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
        adj = {i: [] for i in range(numCourses)}
        in_degree = [0] * numCourses

        for course, pre in prerequisites:
            adj[pre].append(course)
            in_degree[course] += 1

        queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
        count = 0

        while queue:
            curr = queue.popleft()
            count += 1

            for neighbor in adj[curr]:
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)

        return count == numCourses

#include <vector>
#include <queue>

class Solution {
public:
    bool canFinish(int numCourses, std::vector<std::vector<int>>& prerequisites) {
        std::vector<std::vector<int>> adj(numCourses);
        std::vector<int> inDegree(numCourses, 0);

        for (const auto& pre : prerequisites) {
            adj[pre[1]].push_back(pre[0]);
            inDegree[pre[0]]++;
        }

        std::queue<int> q;
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) q.push(i);
        }

        int count = 0;
        while (!q.empty()) {
            int curr = q.front();
            q.pop();
            count++;

            for (int neighbor : adj[curr]) {
                if (--inDegree[neighbor] == 0) {
                    q.push(neighbor);
                }
            }
        }

        return count == numCourses;
    }
};

Complexity Analysis:

• Time Complexity: O(V + E) where V is the number of courses and E is the number of prerequisites. We process each vertex and edge once.
• Space Complexity: O(V + E) for storing the graph adjacency list and the queue.

Where it breaks: If there is a cycle, the nodes in the cycle will never hit in-degree 0, so they will never enter the queue, making count < numCourses at loop exit.

Common Mistakes

• Incorrectly defining edge direction. If you add edges as course -> prerequisite, your topological sort direction is reversed. Keep dependencies clear: prerequisite -> course.
• Not backtracking/resetting state in DFS. If you do not mark visiting nodes as safe 2 after returning, subsequent traversals will evaluate them as active cycle nodes, causing false negatives.
• Forgetting that the graph can be disconnected. You must initiate the cycle check from all unvisited nodes, not just index 0.

Frequently Asked Questions

What is the difference between Course Schedule I and II? Course Schedule I asks for a boolean (can you complete all courses). Course Schedule II (LeetCode 210) asks for the actual topological order. Kahn’s algorithm is ideal for II because the sequence of popped nodes is the sorted order.

Can we solve this using Union-Find? No. Union-Find only detects cycles in undirected graphs. In directed graphs, dependencies like a -> b and c -> b are valid, but Union-Find would falsely flag them as a cycle because they connect.

What does this problem test in interviews? It tests your understanding of directed graphs, cycle detection, topological sorting, and dependency management.

← All Problems