algoadvance

You are required to determine if it is possible for a student to finish all courses given the prerequisites for each course. This is a classic problem of finding a cycle in a directed graph.

Problem:

There are a total of numCourses courses labeled from 0 to numCourses-1. Some courses may have prerequisites, for example, to take course 0 you have to first take course 1, which is expressed as a pair: [0, 1].

Given the total number of courses numCourses and a list of prerequisite pairs prerequisites, return true if you can finish all courses. Otherwise, return false.

Example:

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.

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 have finished course 1. So it is impossible.

Clarifying Questions

1. Can numCourses be zero or negative?
   • No, numCourses will always be a positive integer.
2. Can a course be its own prerequisite?
   • No, we won’t have cases where a course is a prerequisite for itself in the input.
3. Can we assume the input is valid and the pairs are well-formed?
   • Yes, we can assume the input will always be valid and no extra validation is needed for input format.

Strategy

1. Graph Representation:
   • We will represent the courses and their prerequisites as a directed graph using an adjacency list.
2. Cycle Detection using DFS:
   • To determine if we can complete all courses, we need to detect if there is a cycle in the graph.
   • A cycle indicates that there are courses which depend on each other circularly, making it impossible to complete them.
3. Visit States:
   • We’ll use three states to track visiting status of nodes during DFS:
     • Not Visited (0)
     • Visiting (-1) (the current path being visited)
     • Visited (1) (whole graph starting from this node has been visited)
4. Algorithm:
   • Construct the adjacency list for the graph.
   • Traverse each node using DFS to detect cycles.
   • If a cycle is detected during the DFS, return false.
   • If no cycle is detected, return true.

Code

def canFinish(numCourses, prerequisites):
    from collections import defaultdict
    
    # Creating the adjacency list
    graph = defaultdict(list)
    for dest, src in prerequisites:
        graph[src].append(dest)

    # Visitation states: 0 = unvisited, 1 = visiting, 2 = visited
    visit = [0] * numCourses

    def dfs(course):
        if visit[course] == -1:  # currently visiting, cycle detected
            return False
        if visit[course] == 1:   # already visited, no need to visit again
            return True
        
        # Mark the course as being visited
        visit[course] = -1
        
        for neighbor in graph[course]:
            if not dfs(neighbor):
                return False
        
        # Mark the course as fully visited
        visit[course] = 1
        return True

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

Time Complexity

• Time complexity: O(V + E), where V is the number of vertices (courses) and E is the number of edges (prerequisites). Each node and edge is processed once.
• Space complexity: O(V + E) for the adjacency list and O(V) for the visit list.

This solution efficiently determines whether it is possible to complete all courses given the prerequisites by leveraging graph traversal techniques to detect cycles.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?