Introduction

In this blog post, we will explore how to solve the LeetCode problem "207" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai. For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1. Return true if you can finish all courses. Otherwise, return false. Example 1: Input: numCourses = 2, prerequisites = [[1,0]] Output: true Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible. Example 2: Input: numCourses = 2, prerequisites = [[1,0],[0,1]] Output: false Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible. Constraints: 1 <= numCourses <= 2000 0 <= prerequisites.length <= 5000 prerequisites[i].length == 2 0 <= ai, bi < numCourses All the pairs prerequisites[i] are unique.

Explanation

Here's a breakdown of the solution:

• Detect Cycles: The core idea is to represent the course dependencies as a directed graph and detect cycles. If a cycle exists, it means there's a circular dependency, making it impossible to finish all courses.
• Topological Sort (using DFS): We use Depth-First Search (DFS) to perform a topological sort. The DFS algorithm explores each node and its neighbors, marking nodes as "visiting" and "visited." If we encounter a "visiting" node during the DFS traversal, it indicates a cycle.

• Adjacency List: An adjacency list is utilized to represent the graph efficiently.

• Time and Space Complexity: O(V + E), where V is the number of courses (vertices) and E is the number of prerequisites (edges).

Code

    def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    """
    Determines if it is possible to finish all courses given the prerequisites.

    Args:
        numCourses: The total number of courses.
        prerequisites: A list of prerequisites where prerequisites[i] = [ai, bi]
            indicates that you must take course bi first if you want to take course ai.

    Returns:
        True if you can finish all courses, False otherwise.
    """

    # Create an adjacency list to represent the graph
    adj_list = [[] for _ in range(numCourses)]
    for course, pre in prerequisites:
        adj_list[pre].append(course)

    # Use DFS to detect cycles
    visited = [0] * numCourses  # 0: unvisited, 1: visiting, 2: visited

    def dfs(course):
        # If the course is currently being visited, there is a cycle
        if visited[course] == 1:
            return False

        # If the course has already been visited, no need to visit again
        if visited[course] == 2:
            return True

        # Mark the course as being visited
        visited[course] = 1

        # Visit all the neighbors of the course
        for neighbor in adj_list[course]:
            if not dfs(neighbor):
                return False

        # Mark the course as visited
        visited[course] = 2
        return True

    # Check for cycles starting from each course
    for course in range(numCourses):
        if not dfs(course):
            return False

    return True