{ }DevToolsDaily
ToolsInterview
Problems
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

Course Schedule – Solution & Complexity

Interview solutions
/
Course Schedule

1. Understand the Goal

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

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. Build the Algorithm

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

4. Check Edge Cases

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

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

FAQ

See also

Practice Course Schedule online (run code in the browser)Number of Islands solution (medium)Rotting Oranges solution (medium)Clone Graph solution (medium)Network Delay Time solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?