The problem of checking whether it is possible to finish all courses based on prerequisites can be solved using a topological sorting approach. Here’s a Python implementation:

from typing import List

def can_finish_courses(numCourses: int, prerequisites: List[List[int]]) -> bool:
    # Create a graph to represent the prerequisites using an adjacency list
    graph = {i: [] for i in range(numCourses)}
    in_degree = [0] * numCourses

    # Populate the graph and in-degree array
    for course, prereq in prerequisites:
        in_degree[course] += 1
        graph[prereq].append(course) # an edge from prereq to course

    # Perform topological sorting using a queue
    queue = [i for i in range(numCourses) if in_degree[i] == 0]
    while queue:
        current_course = queue.pop(0)
        numCourses -= 1  # Decrement the count of remaining courses

        # Update in-degree and enqueue neighbors
        for neighbor in graph[current_course]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    # If there are remaining courses, it means there is a cycle in the graph
    return numCourses == 0

# Example usage:
# Example 1:
numCourses1 = 2
prerequisites1 = [[1, 0]]
print(can_finish_courses(numCourses1, prerequisites1))  # Output: True

# Example 2:
numCourses2 = 2
prerequisites2 = [[1, 0], [0, 1]]
print(can_finish_courses(numCourses2, prerequisites2))  # Output: False

# Example 3:
numCourses3 = 4
prerequisites3 = [[1, 0], [2, 1], [2, 3], [3, 0]]
print(can_finish_courses(numCourses3, prerequisites3))  # Output: True

This solution builds a graph from the prerequisites, calculates the in-degrees of each node, and then performs topological sorting using a queue. If all courses can be visited and removed from the graph, it means there is no cycle, and it is possible to finish all courses. Otherwise, there is a cycle, and it is not possible to finish all courses. The time complexity of this solution is O(V + E), where V is the number of courses and E is the number of prerequisites. The space complexity is O(V + E).

Time complexity

Here’s a breakdown of the time complexity:

  1. Building the Graph and In-Degree Array:
    • The loop that populates the graph and in-degree array iterates through each prerequisite, taking O(E) time, where E is the number of prerequisites.
  2. Performing Topological Sorting:
    • The while loop performs topological sorting using a queue. In the worst case, every course needs to be processed, and every prerequisite is considered once. So, the loop iterates O(V + E) times.
  3. Updating In-Degree and Enqueuing Neighbors:
    • In each iteration of the while loop, the in-degree of each neighbor is updated. In the worst case, every prerequisite is considered once, resulting in O(E) time complexity.

The dominant factor is the O(V + E) term, and the overall time complexity is O(V + E).

It’s important to note that this solution assumes a constant-time queue operation. In practice, using a deque or a priority queue may have a slightly different impact on the constant factors, but the asymptotic complexity remains O(V + E).

Space complexity

The space complexity of the provided solution is O(V + E), where V is the number of courses and E is the number of prerequisites.

  1. Graph Representation:
    • The graph dictionary is used to represent the prerequisites as an adjacency list.
    • In the worst case, each course might have prerequisites, and thus, the total number of edges (E) is the sum of in-degrees for all nodes.
    • Therefore, the space complexity for representing the graph is O(E).
  2. In-Degree Array:
    • The in_degree list is used to store the in-degree of each course, indicating how many prerequisites it has.
    • The length of in_degree is equal to the number of courses (V).
    • Therefore, the space complexity for storing in-degrees is O(V).
  3. Queue:
    • The queue list is used to perform topological sorting.
    • In the worst case, all courses are initially added to the queue, and thus, the space complexity for the queue is O(V).

The overall space complexity is the sum of these components, which is O(V + E). This is dominated by the space required to represent the graph and the in-degree array. The queue’s contribution is relatively smaller since it depends on the number of courses (V) rather than the number of prerequisites (E).