{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Course Schedule – Solution & Complexity

Interview solutions
/
Course Schedule

Watch: Course Schedule with topological sort

Model courses as a graph where each prerequisite points to the course it unlocks. You can finish everything only if there's no cycle. Kahn's algorithm takes courses with no remaining prerequisites, removes their edges, and repeats; if every course gets taken, the answer is true. O(V + E).

Solution Walkthrough

  1. Step 1: Understand the Goal

    • Identify the required output and the state that changes.
    • Use the examples to rule out tempting but incorrect interpretations.

  2. Step 2: Choose the Core Pattern

    • This problem is best exposed by Kahn topological sort removes zero-indegree courses.
    • Maintain only the state needed for the next operation.

  3. Step 3: Build the Algorithm

    • Process each state once when possible.
    • Record state before scheduling dependent work to avoid duplicates.

  4. Step 4: Check Edge Cases

    • Verify the smallest input, impossible cases, and repeated values where allowed.
    • Keep output ordering deterministic.

  5. Step 5: Final Solution and Complexity

    • Time complexity is O(V + E).
    • Space complexity is O(V + E).
    def can_finish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    graph = [[] for _ in range(numCourses)]
    indegree = [0] * numCourses
    for course, prerequisite in prerequisites:
        graph[prerequisite].append(course)
        indegree[course] += 1
    queue = [i for i in range(numCourses) if indegree[i] == 0]
    head = completed = 0
    while head < len(queue):
        course = queue[head]; head += 1; completed += 1
        for nxt in graph[course]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0: queue.append(nxt)
    return completed == numCourses
Learn the Graph Traversal pattern: recognition cues, invariant, and ordered practice →

FAQ

See also

Practice Course Schedule online (run code in the browser)Number of Islands solution (medium)01 Matrix solution (medium)Alien Dictionary solution (hard)Course Schedule II solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?