Similar Problems
Similar Problems not available
Course Schedule  Leetcode Solution
LeetCode: Course Schedule Leetcode Solution
Difficulty: Medium
Topics: graph depthfirstsearch breadthfirstsearch
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 depthfirst search (DFS) algorithm. The idea behind the algorithm is as follows:

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

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

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.

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.

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.
Course Schedule Solution Code
1