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 can use Depth-First Search (DFS) to detect cycles in the graph. During the DFS traversal, we will mark each node with one of three states: unvisited, visiting, or visited. If we encounter a node that is already in the visiting state, it means we've found a cycle.

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