What is the time and space complexity of Course Schedule?

Time complexity: O(V + E). Space complexity: O(V + E).

Course Schedule

Med

Code

Loading editor...

Tap Analyze to see visualization

Click Analyze to visualize

See step-by-step execution, variables, and output

Variables

Run code to see variables

Output

Console output will appear here

Press Space to start•← → to step•? all shortcuts

Solution Guide: Course Schedule

Approach

Build directed edges pre -> course and indegree counts. Remove zero-indegree nodes repeatedly; if all nodes are processed, there is no cycle.

Complexity Analysis

Time: O(V + E)
Space: O(V + E)

Pattern

Topological Sort (Kahn)

Why It Works

A valid course order exists only if no cycle prevents completing prerequisites. Kahn’s process consumes all reachable zero-indegree courses only when graph is acyclic.

Updated Mar 2026