Course Schedule - Leetcode Solution

The Course Schedule problem on LeetCode (Problem No. 207) asks us to determine whether it is possible to complete all the courses in a given set of prerequisites.

The problem statement and input format can be found on the LeetCode website. The problem essentially boils down to checking whether the given set of prerequisite relationships forms a directed acyclic graph (DAG). If there is a cycle in the graph, it means that there is a circular dependence between courses, and we cannot complete all the courses.

One way to approach this problem is to use a topological sort algorithm on the given directed graph. A topological sort of a DAG is a linear ordering of its nodes such that for every directed edge (u, v), node u comes before node v in the ordering. If the graph has a topological order, it means that there is no circular dependence between its nodes.

We can implement a topological sort using a modified depth-first search (DFS) algorithm. The idea behind the algorithm is as follows:

1. Create an adjacency list representation of the graph, where each node has a list of its outgoing edges.

2. Initialize a visited array to keep track of the nodes we have already visited, and a stack to keep track of the topological order.

3. For each unvisited node in the graph, call a DFS function that explores all its outgoing edges and adds the node to the stack after visiting all its neighbors.

4. If we encounter a visited node during the DFS function, it means that there is a cycle in the graph, and we can return False.

5. If we have visited all the nodes in the graph without encountering a cycle, it means that we have a valid topological order, and we can return True.

Here is the Python code for the solution as explained above:

from collections import defaultdict

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # Step 1: Create adjacency list representation of the graph
        graph = defaultdict(list)
        for pair in prerequisites:
            graph[pair[1]].append(pair[0])
        
        # Step 2: Initialize visited and stack arrays
        visited = [False] * numCourses
        stack = [False] * numCourses
        
        # Step 3: Call DFS function for each unvisited node
        for node in range(numCourses):
            if not visited[node]:
                if self.hasCycle(node, graph, visited, stack):
                    return False
        
        # Step 5: If we reach here, the graph is acyclic
        return True
    
    # Helper function for DFS traversal of the graph
    def hasCycle(self, node: int, graph: defaultdict(list), visited: List[bool], stack: List[bool]) -> bool:
        # Mark current node as visited and add to stack
        visited[node] = True
        stack[node] = True
        
        # Recursively visit all neighbors of current node
        for neighbor in graph[node]:
            if not visited[neighbor]:
                if self.hasCycle(neighbor, graph, visited, stack):
                    return True
            elif stack[neighbor]:
                return True
        
        # Remove current node from stack after visiting all its neighbors
        stack[node] = False
        
        # If we reach here, there is no cycle in the current subgraph
        return False

The time complexity of the algorithm is O(N + E), where N is the number of nodes and E is the number of edges in the graph. This is because we visit each node and edge in the graph exactly once. The space complexity is also O(N + E), because we use adjacency list representation of the graph and other auxiliary arrays.

In conclusion, the Course Schedule problem on LeetCode can be solved using a topological sort algorithm based on DFS. We check for cycles in the graph during the DFS traversal, and return False if a cycle is found. Otherwise, we return True if the graph is acyclic.

1