medium Course Schedule

Problem Statement

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

Return true if it's possible to finish all the courses given these prerequisites. Otherwise, return false.

Examples

Example 1:

• Input: numCourses = 3, prerequisites = [[2, 0], [2, 1]]
• Expected Output: true
• Justification: You can take course 0 and course 1 first, then take course 2.

Example 2:

• Input: numCourses = 4, prerequisites = [[1, 0], [2, 1], [3, 2], [1, 3]]
• Expected Output: false
• Justification: There is a cycle in the prerequisites: course 1 requires course 3, which requires course 2, which requires course 1.

Example 3:

• Input: numCourses = 5, prerequisites = [[1, 0], [2, 1], [3, 2], [4, 3]]
• Expected Output: true
• Justification: You can take courses in the order 0, 1, 2, 3, and 4 without any conflicts.

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.

Solution

To solve this problem, we can model it as a graph where each course is a node, and each prerequisite is a directed edge. We need to check if there are any cycles in this graph. A cycle would mean that it is impossible to complete the courses. We use Kahn's algorithm (BFS topological sort) to detect cycles. The idea is to repeatedly remove nodes whose in-degree is zero: such nodes have no remaining prerequisites and can be taken now. Each time we remove a node, we decrement the in-degree of every course that depends on it. If we manage to remove all numCourses nodes, the graph is acyclic and every course can be finished; if the queue empties while nodes still have a non-zero in-degree, those nodes sit on a cycle and the answer is false.

This approach is effective because it efficiently checks for cycles and uses a graph traversal method that ensures all nodes and edges are examined. By marking the states of nodes, we can quickly detect cycles and avoid redundant work.

Step-by-step Algorithm

1. Initialize inDegree and adjList:

   • Create an array inDegree of size numCourses initialized to 0. This array will keep track of the number of prerequisites each course has.
   • Create an adjacency list adjList as a dictionary (or hashmap) where each key is a course and its value is a list of courses that depend on it.

2. Fill inDegree and adjList:

   • Iterate through the prerequisites array. For each pair [a, b], increment inDegree[a] by 1 (since course a has one more prerequisite). Add a to the list of b in adjList (since course a depends on course b).

3. Initialize the queue:

   • Create a queue and add all courses with inDegree of 0 (i.e., courses with no prerequisites).

4. Process the queue:

   • Initialize a counter completedCourses to 0.
   • While the queue is not empty:
     • Dequeue a course from the front of the queue.
     • Increment completedCourses by 1.
     • For each course that depends on the dequeued course (found in adjList):
       • Decrement the inDegree of that course by 1.
       • If inDegree of that course becomes 0, enqueue it.

5. Check if all courses are completed:

   • If completedCourses equals numCourses, return true (all courses can be completed).
   • Otherwise, return false (it's not possible to complete all courses due to a cycle).

Algorithm Walkthrough

Let's go through the algorithm step-by-step for the input:

• numCourses = 5
• prerequisites = [[1, 0], [2, 1], [3, 2], [4, 3]]

1. Initialize inDegree and adjList:

   • inDegree = [0, 0, 0, 0, 0]
   • adjList = {0: [], 1: [], 2: [], 3: [], 4: []}

2. Fill inDegree and adjList:

   • For [1, 0]:
     • inDegree = [0, 1, 0, 0, 0]
     • adjList = {0: [1], 1: [], 2: [], 3: [], 4: []}
   • For [2, 1]:
     • inDegree = [0, 1, 1, 0, 0]
     • adjList = {0: [1], 1: [2], 2: [], 3: [], 4: []}
   • For [3, 2]:
     • inDegree = [0, 1, 1, 1, 0]
     • adjList = {0: [1], 1: [2], 2: [3], 3: [], 4: []}
   • For [4, 3]:
     • inDegree = [0, 1, 1, 1, 1]
     • adjList = {0: [1], 1: [2], 2: [3], 3: [4], 4: []}

3. Initialize the queue:

   • queue = [0] (only course 0 has no prerequisites)

4. Process the queue:

   • Initialize completedCourses = 0
   • While queue is not empty:
     • Dequeue course 0:
       • queue = []
       • Increment completedCourses to 1
       • For course 1 (dependent on 0):
         • Decrement inDegree[1] to 0
         • Enqueue course 1
       • queue = [1]
     • Dequeue course 1:
       • queue = []
       • Increment completedCourses to 2
       • For course 2 (dependent on 1):
         • Decrement inDegree[2] to 0
         • Enqueue course 2
       • queue = [2]
     • Dequeue course 2:
       • queue = []
       • Increment completedCourses to 3
       • For course 3 (dependent on 2):
         • Decrement inDegree[3] to 0
         • Enqueue course 3
       • queue = [3]
     • Dequeue course 3:
       • queue = []
       • Increment completedCourses to 4
       • For course 4 (dependent on 3):
         • Decrement inDegree[4] to 0
         • Enqueue course 4
       • queue = [4]
     • Dequeue course 4:
       • queue = []
       • Increment completedCourses to 5

5. Check if all courses are completed:

   • completedCourses = 5
   • Since completedCourses equals numCourses, return true

Code

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

public class Solution {

  // Method to check if all courses can be finished
  public boolean canFinish(int numCourses, int[][] prerequisites) {
    // Create an array to store the number of prerequisites for each course
    int[] inDegree = new int[numCourses];
    // Create an adjacency list to store which courses depend on a given course
    List> adjList = new ArrayList<>();

    for (int i = 0; i < numCourses; i++) {
      adjList.add(new ArrayList<>());
    }

    // Fill the inDegree array and adjacency list based on prerequisites
    for (int[] pair : prerequisites) {
      int course = pair[0];
      int prereq = pair[1];
      inDegree[course]++;
      adjList.get(prereq).add(course);
    }

    // Use a queue to keep track of courses with no prerequisites
    Queue queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
      if (inDegree[i] == 0) {
        queue.add(i);
      }
    }

    // Process courses with no prerequisites
    int completedCourses = 0;
    while (!queue.isEmpty()) {
      int course = queue.poll();
      completedCourses++;
      for (int nextCourse : adjList.get(course)) {
        inDegree[nextCourse]--;
        if (inDegree[nextCourse] == 0) {
          queue.add(nextCourse);
        }
      }
    }

    // If all courses are completed, return true
    return completedCourses == numCourses;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Example 1
    int numCourses1 = 3;
    int[][] prerequisites1 = { { 2, 0 }, { 2, 1 } };
    System.out.println(solution.canFinish(numCourses1, prerequisites1)); // true

    // Example 2
    int numCourses2 = 4;
    int[][] prerequisites2 = { { 1, 0 }, { 2, 1 }, { 3, 2 }, { 1, 3 } };
    System.out.println(solution.canFinish(numCourses2, prerequisites2)); // false

    // Example 3
    int numCourses3 = 5;
    int[][] prerequisites3 = { { 1, 0 }, { 2, 1 }, { 3, 2 }, { 4, 3 } };
    System.out.println(solution.canFinish(numCourses3, prerequisites3)); // true
  }
}

Complexity Analysis

Time Complexity

• Building the graph: We iterate through the prerequisites array to build the adjacency list and in-degree array. This takes time, where E is the number of edges (or prerequisites).
• Processing the graph: We use a queue to process nodes with zero in-degrees. In the worst case, we process all nodes and all edges once. This step takes time, where V is the number of vertices (courses).

Therefore, the overall time complexity is .

Space Complexity

• Adjacency list: The adjacency list representation of the graph requires space.
• In-degree array: The in-degree array requires space.
• Queue: In the worst case, the queue can hold up to nodes.

Thus, the overall space complexity is .