Obsidian Notes

8. Course Schedule

3 min read

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] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

  • 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 <= ai, bi < numCourses
  • All the pairs prerequisites[i] are unique.

Approach - DFS

  • We maintain visited where 1 is we are visiting and 2 is we have visited
  • Main point is that if we have a cycle in graph then it is not possible cause each one requires other to get completed so it never completes
  • We have a list where index is the course and list to that index is the list of courses that becomes available after completing the index course
  • We loop through and check if we have cycle for each course then in cycle method we run the has cycle for the courses that gets unlocked after the current index
  • Time: O(m*n), Space: O(m*n)
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++)
            graph.add(new ArrayList<>());
 
        for (int[] pre : prerequisites) {
            graph.get(pre[1]).add(pre[0]);
        } 
 
        int[] visited = new int[numCourses];
 
        for (int i = 0; i < numCourses; i++) {
            if (hasCycle(graph,visited,i)) {
                return false;
            }
        }
 
        return true;   
    }
 
    public boolean hasCycle(List<List<Integer>> graph, int[] visited, int course) {
        //1 -> visiting 2 -> visited, still 1 means it is true
        if (visited[course] == 1)
            return true; //cycle
        if (visited[course] == 2)
            return false;
 
        visited[course] = 1; //visiting
        // these are all the courses now unlocked we can check the cycle for them
        for (int next: graph.get(course)) {
            if (hasCycle(graph,visited,next))
                return true;
        }         
 
        visited[course] = 2; //we have visited still no cycle
        return false;
    }
}

Approach - BFS (Kahn’s algorithm)

Backlinks