Course Schedule

MEDIUM

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_i, b_i] indicates that you must take course b_i first if you want to take course a_i.

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

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

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take. 
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Constraints:

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= a_i, b_i < numCourses
All the pairs prerequisites[i] are unique.

Approaches

Checkout 3 different approaches to solve Course Schedule. Click on different approaches to view the approach and algorithm in detail.

DFS with Adjacency Matrix

This approach uses an adjacency matrix to represent the course prerequisites and performs DFS to detect cycles in the graph.

Algorithm

Create an adjacency matrix from prerequisites
For each course:
- Perform DFS with visited and recursion stack arrays
- If cycle is detected, return false
Return true if no cycles found

In this approach, we first create an adjacency matrix of size numCourses × numCourses to represent the prerequisites. For each prerequisite pair [a, b], we set matrix[a][b] = 1 indicating course b is required for course a. Then we perform DFS starting from each course to detect if there's a cycle in the graph.

class Solution {
    private boolean dfs(int[][] matrix, boolean[] visited, boolean[] recursionStack, int course) {
        if (recursionStack[course]) return true; // cycle detected
        if (visited[course]) return false;
        
        visited[course] = true;
        recursionStack[course] = true;
        
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[course][i] == 1 && dfs(matrix, visited, recursionStack, i)) {
                return true;
            }
        }
        
        recursionStack[course] = false;
        return false;
    }
    
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[][] matrix = new int[numCourses][numCourses];
        for (int[] pre : prerequisites) {
            matrix[pre[0]][pre[1]] = 1;
        }
        
        boolean[] visited = new boolean[numCourses];
        boolean[] recursionStack = new boolean[numCourses];
        
        for (int i = 0; i < numCourses; i++) {
            if (dfs(matrix, visited, recursionStack, i)) {
                return false;
            }
        }
        return true;
    }
}```

Complexity Analysis

Time Complexity: O(n^2) where n is the number of courses, as we need to traverse the entire matrixSpace Complexity: O(n^2) for the adjacency matrix + O(n) for recursion stack

Pros and Cons

Pros:

Simple to understand and implement
Good for dense graphs
Easy to modify for additional requirements

Cons:

High space complexity due to adjacency matrix
Not efficient for sparse graphs
Unnecessary space usage when prerequisites are few

Code Solutions

Checking out 4 solutions in different languages for Course Schedule. Click on different languages to view the code.

public class Solution {
    public bool CanFinish(int numCourses, int[][] prerequisites) {
        var g = new List < int > [numCourses];
        for (int i = 0; i < numCourses; ++i) {
            g[i] = new List < int > ();
        }
        var indeg = new int[numCourses];
        foreach(var p in prerequisites) {
            int a = p[0], b = p[1];
            g[b].Add(a);
            ++indeg[a];
        }
        var q = new Queue < int > ();
        for (int i = 0; i < numCourses; ++i) {
            if (indeg[i] == 0) {
                q.Enqueue(i);
            }
        }
        var cnt = 0;
        while (q.Count > 0) {
            int i = q.Dequeue();
            ++cnt;
            foreach(int j in g[i]) {
                if (--indeg[j] == 0) {
                    q.Enqueue(j);
                }
            }
        }
        return cnt == numCourses;
    }
}

Video Solution

Watch the video walkthrough for Course Schedule

Algorithms:

Depth-First SearchBreadth-First SearchTopological Sort

Data Structures:

Graph

Companies:

ByteDance |DoorDash |Flipkart |Intuit |