Big O Practice: Course Schedule

def can_finish(num_courses, prerequisites):
    graph = [[] for _ in range(num_courses)]
    for a, b in prerequisites:
        graph[b].append(a)
    UNVISITED, VISITING, DONE = 0, 1, 2
    state = [UNVISITED] * num_courses

    def dfs(node):
        if state[node] == VISITING:
            return False
        if state[node] == DONE:
            return True
        state[node] = VISITING
        for nb in graph[node]:
            if not dfs(nb):
                return False
        state[node] = DONE
        return True

    for i in range(num_courses):
        if not dfs(i):
            return False
    return True

Variables

• v - number of vertices (courses)
• e - number of edges (prerequisites)

Explanation

Each vertex is visited once via the three-color DFS, each edge traversed once - **O(V + E)** time. The adjacency list itself is **O(V + E)** space; the recursion stack is bounded by `V`. Combined: **O(V + E)**.

More Big O practice problems · Today's daily problem