MediumDepth-First SearchBreadth-First SearchGraphTopological SortUpdated Sep 2026

210. Course Schedule II

Asked at Apple, Netflix, Salesforce, Uber and 3 more

Difficulty

Medium

Time

O(V + E)

Space

O(V + E)

Pattern

Depth-First Search

Companies

7

Problem

You must finish numCourses courses, numbered from 0 to numCourses - 1. Some courses have requirements: the pair [a, b] in prerequisites means you must complete course b before you can take course a.

Return a list of all courses in an order that respects every requirement. If several orders are valid, any one of them is accepted.

If no valid order exists — that is, the requirements form a cycle and some course can never be taken — return an empty list [].

Requirements as arrows

prerequisitesab10203132Each row says: take a, but only after b0 → 10 → 21 → 32 → 3Course 0 unlocks 1 and 2; both of them unlock 3
An arrow b → a means course b must be finished before course a.

Constraints

  • ●1 <= numCourses <= 2000
  • ●0 <= prerequisites.length <= numCourses * (numCourses - 1)
  • ●prerequisites[i].length == 2
  • ●0 <= ai, bi < numCourses
  • ●ai != bi
  • ●All the pairs [ai, bi] are distinct.

Examples

Example 1
InputnumCourses = 2, prerequisites = [[1,0]]
Output[0,1]
WhyCourse 1 needs course 0 first. Taking 0 and then 1 satisfies the only rule, so [0,1] works.
Example 2
InputnumCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output[0,2,1,3]
WhyCourse 0 has no requirements, so it goes first. Courses 1 and 2 both need only 0, so they can come in either order. Course 3 needs both 1 and 2, so it must be last. [0,2,1,3] respects all of this.
Example 3
InputnumCourses = 1, prerequisites = []
Output[0]
WhyThere is a single course with no requirements, so the only order is [0].

Asked At

7 companies
CompanyDifficulty
AppleMediumView all Apple questions →
NetflixMediumView all Netflix questions →
SalesforceMediumView all Salesforce questions →
UberMediumView all Uber questions →
WalmartMediumView all Walmart questions →
AndurilMediumView all Anduril questions →
SnowflakeMediumView all Snowflake questions →

How to Think About It

1

Model this as a directed graph: each course is a node, each prerequisite [dest, src] is an edge from src to dest (you must take src before dest).

2

Topological sort = ordering nodes so all edges go forward. Use Kahn's algorithm (BFS): start with nodes that have no prerequisites (in-degree 0), process them, then process their neighbors.

3

Why Kahn's works: nodes with in-degree 0 have all prerequisites satisfied. Process them, remove their edges, and new nodes may become in-degree 0. Repeat until done.

4

Cycle detection: if the result has fewer than n nodes, a cycle exists. You can't finish all courses.

Optimal Approach

Step 1: Build adjacency list and compute in-degrees.
Step 2: Add all nodes with in-degree 0 to a queue.
Step 3: Process queue (BFS):

  • Dequeue a node, add to result
  • For each neighbor, decrement in-degree
  • If in-degree becomes 0, enqueue
    Step 4: If result length < n, cycle exists → return [].

Kahn's algorithm naturally detects cycles: if you can't process all nodes, there's a cycle.

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

Kahn's algorithm: always take a free course

in-degree01120123Course 0 has in-degree 0, so it is ready; the othersstill wait on somethingqueue0frontbackPut every ready course in the queueorder01230123Pop 0, then 1, then 2, then 3 — all four courses areplacedpop a ready course → append to orderfor each neighbor: in-degree − 1if in-degree hits 0 → push to queuelen(order) < n means a cycle → return []
Start with courses that have no unmet requirements, then remove their arrows and repeat.
ComplexityTime O(V + E)Space O(V + E)Each course and each prerequisite edge is handled a constant number of times, and we store the graph plus the queue and result.

What Trips People Up in Real Interviews

1

Confusing this with Course Schedule I. This problem asks for the order, not just whether it's possible. You need topological sort, not just cycle detection.

2

Not handling the case where no valid order exists (cycle). Return an empty array, not null or an error.

3

Forgetting to include courses with no prerequisites. They should appear in the order (their in-degree is 0).

4

Not handling the case where the result array is shorter than the number of courses. This means a cycle exists — return empty.

5

Reversing the edge direction. If course A requires course B, the edge is B → A (B must come before A). Getting this wrong reverses the topological order entirely.

Solution Code

O(V + E) time
from collections import deque

def findOrder(numCourses, prerequisites):
    adj = [[] for _ in range(numCourses)]
    in_degree = [0] * numCourses
    for dest, src in prerequisites:
        adj[src].append(dest)
        in_degree[dest] += 1
    q = deque([i for i in range(numCourses) if in_degree[i] == 0])
    order = []
    while q:
        node = q.popleft()
        order.append(node)
        for neighbor in adj[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                q.append(neighbor)
    return order if len(order) == numCourses else []

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Course Schedule II problem?

There are a total of n courses you can take, with some courses having prerequisites. Return the ordering of courses you should take to finish all courses. If impossible, return an empty array. This problem tests topological sorting.

How do you solve Course Schedule II?

The optimal approach runs in O(V + E) time and O(V + E) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Course Schedule II?

Course Schedule II is asked at Apple, Netflix, Salesforce, Uber, Walmart, Anduril, Snowflake. It is a medium difficulty problem.

What are common mistakes on Course Schedule II?
  • Confusing this with Course Schedule I. This problem asks for the order, not just whether it's possible. You need topological sort, not just cycle detection.
  • Not handling the case where no valid order exists (cycle). Return an empty array, not `null` or an error.
  • Forgetting to include courses with no prerequisites. They should appear in the order (their in-degree is 0).
  • Not handling the case where the result array is shorter than the number of courses. This means a cycle exists — return empty.
  • Reversing the edge direction. If course A requires course B, the edge is B → A (B must come before A). Getting this wrong reverses the topological order entirely.