We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Course Schedule

Difficulty: Medium

Problem Description

You are given a total of numCourses courses labeled from 0 to numCourses - 1. An array prerequisites indicates which courses must be taken before others. Return true if you can finish all courses; otherwise, return false.

Key Insights

  • The problem can be modeled as a directed graph where courses are nodes and prerequisites are directed edges.
  • A cycle in the graph indicates that it's impossible to complete the courses, as it creates a loop of dependencies.
  • Depth-First Search (DFS) or Kahn's algorithm for topological sorting can be used to detect cycles in the graph.

Space and Time Complexity

Time Complexity: O(V + E), where V is the number of courses and E is the number of prerequisites.
Space Complexity: O(V + E) for storing the graph and tracking visited nodes.

Solution

To solve this problem, we can use Depth-First Search (DFS) to explore each course and its prerequisites. We maintain a visited array to keep track of courses being processed and those that have been completed. If we encounter a course that is currently being processed, it indicates a cycle, and we return false. If we can process all courses without encountering a cycle, we return true.

Code Solutions

def canFinish(numCourses, prerequisites):
    from collections import defaultdict
    
    graph = defaultdict(list)
    for a, b in prerequisites:
        graph[b].append(a)

    visited = [0] * numCourses

    def dfs(course):
        if visited[course] == 1:
            return False
        if visited[course] == 2:
            return True
        
        visited[course] = 1  # Mark as being processed
        for neighbor in graph[course]:
            if not dfs(neighbor):
                return False
        visited[course] = 2  # Mark as processed
        return True

    for course in range(numCourses):
        if not dfs(course):
            return False
    return True
← Back to All Questions