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.

Return true if you can finish all courses. Otherwise, return false.

Additional information

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• All the pairs prerequisites[i] are unique.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]

Output: true

Explanation: There are 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 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.

Brute Force (Naive DFS Cycle Detection)

Intuition

The problem of figuring out if we can finish all courses is fundamentally asking: "Is there a cycle in this directed graph?" If Course A requires Course B, and Course B requires Course A, we are stuck forever.

A naive way to check for cycles is to build an adjacency list, mapping each course to its prerequisites. Then, we can run a Depth-First Search (DFS) starting from every single course. We use a visiting set to keep track of the courses in our current DFS path. If we ever encounter a course that is already in our visiting set, we've walked in a circle and found a cycle!

In this brute-force version, we clear our memory of safe paths entirely between checks, meaning we will redundantly re-check the same courses over and over again from different starting points.

Algorithm

1. Create an adjacency list adj mapping each course to an empty list.
2. Populate adj with the prerequisites.
3. Define a recursive helper function has_cycle(crs, visiting):

• If crs is in visiting, a cycle exists. Return True.
• Add crs to visiting.
• Loop through all prerequisites of crs (adj[crs]). Recursively call has_cycle on them.
• If any recursive call returns True, return True.
• Backtrack: Remove crs from visiting so it doesn't falsely trigger a cycle on a completely different branch.
• Return False.

4. Loop i from 0 to numCourses - 1.
5. Call has_cycle(i, set()). If it returns True, return False (because we can't finish the courses).
6. If the loop finishes without finding cycles, return True.

def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
    adj = {i: [] for i in range(num_courses)}
    for crs, pre in prerequisites:
        adj[crs].append(pre)
        
    def has_cycle(crs, visiting):
        if crs in visiting:
            return True
            
        visiting.add(crs)
        
        for pre in adj[crs]:
            if has_cycle(pre, visiting):
                return True
                
        visiting.remove(crs)
        return False
        
    for i in range(num_courses):
        # We naively use a fresh 'visiting' set for every node
        if has_cycle(i, set()):
            return False
            
    return True

Time & Space Complexity

• Time complexity: O(V * (V + E))

• Reason: In the worst case, without caching safely processed nodes, we might traverse the entire graph of Vertices (V) and Edges (E) again for every single starting Vertex.

• Space complexity: O(V + E)

• Reason: The adjacency list takes O(V + E) space. The recursion stack and visiting set take up to O(V) space.

Topological Sort (Kahn's Algorithm BFS) - Optimal

Intuition

To optimize this, we can use Kahn's Algorithm for Topological Sorting. This is a highly efficient, iterative Breadth-First Search (BFS) approach.

Instead of hunting for cycles, we focus on what we can do. We count the "in-degree" (the number of prerequisites) for every course. Any course with an in-degree of 0 has no prerequisites-we can take it immediately!

We put all these 0-in-degree courses into a queue. As we pop a course from the queue (simulating "taking" the course), we look at all the courses that required it, and we subtract 1 from their in-degree. If their in-degree hits 0, they are now unlocked, and we add them to the queue! If we manage to pop numCourses total courses from the queue, we successfully finished the curriculum. If we don't, it means the remaining courses are locked in a cycle.

Algorithm

1. Initialize an adjacency list adj and an indegree array/dictionary for all courses set to 0.
2. Iterate through prerequisites. For [crs, pre], add crs to adj[pre] (because completing pre unlocks crs), and increment indegree[crs] by 1.
3. Initialize a deque (queue).
4. Iterate through all courses. If indegree[i] == 0, append i to the queue.
5. Initialize a completed_courses counter to 0.
6. While the queue is not empty:

• Pop the front course curr.
• Increment completed_courses by 1.
• Iterate through the neighbors in adj[curr].
• Decrement the indegree[neighbor] by 1.
• If indegree[neighbor] reaches 0, append it to the queue.

7. Return True if completed_courses == numCourses, else False.

def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
    # Map each prerequisite to the courses it unlocks
    adj = {i: [] for i in range(num_courses)}
    indegree = {i: 0 for i in range(num_courses)}
    
    for crs, pre in prerequisites:
        adj[pre].append(crs)
        indegree[crs] += 1
        
    # Queue up all courses that have no prerequisites
    q = deque()
    for i in range(num_courses):
        if indegree[i] == 0:
            q.append(i)
            
    completed_courses = 0
    
    # Process courses
    while q:
        curr = q.popleft()
        completed_courses += 1
        
        # Taking 'curr' unlocks its dependent courses
        for neighbor in adj[curr]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                q.append(neighbor)
                
    return completed_courses == num_courses

Time & Space Complexity

• Time complexity: O(V + E)

• Reason: Initializing the adjacency list and in-degrees takes O(E). Finding the initial 0 in-degree nodes takes O(V). Processing the queue visits each node and its edges exactly once, taking O(V + E).

• Space complexity: O(V + E)

• Reason: The adjacency list adj holds all Vertices and Edges. The indegree map and the queue hold at most V elements.