8. Course Schedule

Description

Course Schedule

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;
    }
}

Primary Approach: Kahn’s Algorithm / BFS Topological Sort ($O(V+E)$ Time, $O(V+E)$ Space)

Intuition

Course dependencies form a directed graph where an edge $b\to a$ means course $b$ must be completed before course $a$. Finishing all courses is possible if and only if the directed graph contains no cycles:

1. Indegree Array: Calculate the indegree (number of prerequisite dependencies) for every course.
2. Queue Initialization: Add all courses with an indegree of 0 (courses with no prerequisites) to a Queue.
3. BFS Traversal:
   • Poll a course from the queue and increment a completedCourses counter.
   • For each dependent neighbor, decrement its indegree.
   • If any neighbor’s indegree drops to 0, push it to the queue.
4. Conclusion: If completedCourses == numCourses, all courses can be finished; otherwise, a cycle exists.

import java.util.ArrayDeque;
import java.util.ArrayList;
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<>());
        }
 
        // Build adjacency list (b -> a) and indegree array
        for (int[] pre : prerequisites) {
            int course = pre[0];
            int prereq = pre[1];
            adj.get(prereq).add(course);
            indegree[course]++;
        }
 
        // Queue all courses with 0 prerequisites
        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                queue.add(i);
            }
        }
 
        int completedCourses = 0;
 
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            completedCourses++;
 
            for (int neighbor : adj.get(curr)) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    queue.add(neighbor);
                }
            }
        }
 
        return completedCourses == numCourses;
    }
}
 

Complexity

• Time Complexity: $O(V+E)$ — $V=\text{numCourses}$ and $E=\text{prerequisites.length}$. Every vertex and edge is processed once.
• Space Complexity: $O(V+E)$ — To store the adjacency list graph representation, indegree array, and queue.

---

Alternative Approach: DFS Cycle Detection using 3 States ($O(V+E)$ Time, $O(V+E)$ Space)

Intuition

Detect cycles in a directed graph using Depth-First Search with 3 states:

• 0: Unvisited
• 1: Visiting (currently in the active recursion call stack)
• 2: Visited (fully processed without finding a cycle)

If DFS encounters a neighbor currently in state 1, a back-edge (cycle) exists, making it impossible to finish all courses.

import java.util.ArrayList;
import java.util.List;
 
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        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[] state = new int[numCourses]; // 0 = unvisited, 1 = visiting, 2 = visited
 
        for (int i = 0; i < numCourses; i++) {
            if (state[i] == 0) {
                if (hasCycle(i, adj, state)) {
                    return false;
                }
            }
        }
 
        return true;
    }
 
    private boolean hasCycle(int node, List<List<Integer>> adj, int[] state) {
        if (state[node] == 1) return true;  // Cycle detected
        if (state[node] == 2) return false; // Already verified safe
 
        state[node] = 1; // Mark as currently visiting
 
        for (int neighbor : adj.get(node)) {
            if (hasCycle(neighbor, adj, state)) {
                return true;
            }
        }
 
        state[node] = 2; // Mark as fully processed
        return false;
    }
}
 

Complexity

• Time Complexity: $O(V+E)$ — Every course node and prerequisite dependency edge is visited at most once.
• Space Complexity: $O(V+E)$ — Adjacency list takes $O(V+E)$ space, and recursion stack takes up to $O(V)$ space.

---

Key Interview Discussion Points

• Graph Problem Identification: Frame the problem immediately to the interviewer: “This is a standard Topological Sort problem on a Directed Acyclic Graph (DAG) to check for cyclic dependencies.”
• Kahn’s Algorithm Advantage: BFS (Kahn’s Algorithm) is often preferred because it naturally extends to Course Schedule II where returning the exact course execution order is required.

---

Easy Memory Rule

“Dependencies = Directed Graph $\to$ No Cycle means Valid Order $\to$ Kahn’s BFS (indegree == 0) or DFS State Array (1 = visiting cycle)!”