Course Schedule II

Table of Contents +

Some things must happen in a certain order. You cannot wear shoes before socks. Course Schedule II is that idea turned into a coding question. The interviewer wants to see if you can take a list of “do this before that” rules and turn it into one valid order. That ordering trick has a name, and learning it here will help you in many other problems.

🎯 The Problem

You have to find one valid order to take all the courses. Here are the rules.

  • Courses are labeled 0 to n - 1.
  • Each rule [a, b] means “to take course a, you must first take course b”.
  • Return any order in which you can take all the courses.
  • If no valid order exists, return an empty list.
  • The number of courses pointing into a course is its indegree.
  • A course with indegree 0 needs nothing first, so it is a safe starting point.

For example, with 4 courses and rules [[1,0],[2,0],[3,1],[3,2]], course 0 has no rule. Course 1 and 2 both need 0. Course 3 needs both 1 and 2. So one valid order is 0, 1, 2, 3.

Input:  numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0, 1, 2, 3]


Explanation: 0 has no prerequisite. 1 and 2 need 0. 3 needs 1 and 2.

If the rules form a loop, like 0 needs 1 and 1 needs 0, then no order works. You return an empty list.

Here is the dependency picture as a graph. An arrow from 0 to 1 means 0 must come before 1.

Course 0

Course 1

Course 2

Course 3

🐢 Approach 1: DFS Then Reverse (Alternative)

The idea in one line: go deep from each course, record a course only after everything it leads to, then reverse the list.

The idea:

  • Depth-first search follows one path as far as it goes before backing up.
  • A course belongs in the answer only after every course that depends on it.
  • So recurse into neighbors first, then add the current course, then reverse at the end.

How it works:

  • Visit a course. Recurse into all its neighbors.
  • Once all neighbors are placed, add the current course to a list.
  • Reverse the list to get the order.
  • Track a “currently visiting” mark to catch loops.
  • If you reach a course still on the current path, that is a cycle. No order works.

Why it is weak:

  • The recursion plus the cycle mark is easy to get wrong under pressure.
  • A deep graph can hit the recursion limit.

Here is the DFS-postorder code:

course_schedule_ii_dfs.py
def find_order(num_courses, prerequisites):
    graph = [[] for _ in range(num_courses)]
    for course, pre in prerequisites:
        graph[pre].append(course)
    state, order = [0] * num_courses, []
    def dfs(node):
        if state[node] == 1: return False
        if state[node] == 2: return True
        state[node] = 1
        for nei in graph[node]:
            if not dfs(nei): return False
        state[node] = 2; order.append(node)
        return True
    return order[::-1] if all(dfs(i) for i in range(num_courses)) else []

⚡ Approach 2: Kahn’s Algorithm with BFS (Best)

The idea in one line: peel off courses that are ready right now, one layer at a time, using indegree counts.

The idea:

  • Kahn’s algorithm is a breadth-first topological sort.
  • Topological sort lines up the nodes of a directed graph so every arrow points forward.
  • A course is ready when its indegree is 0, meaning nothing must come before it.

How it works:

  • Count the indegree of every course.
  • Put every course with indegree 0 into a queue.
  • Take a course from the queue. Add it to the answer.
  • For each course that depended on it, lower its indegree by one.
  • If any drops to 0, it just became ready, so push it.
  • When the queue empties, check the answer length.

How it finds a cycle:

  • If you placed every course, you found a valid order.
  • If some are missing, those leftovers were stuck in a loop. Return an empty list.

Why it is clean:

  • No recursion, so no stack limit worry.
  • The length check is the whole cycle test.

Here is a dry run of Kahn’s algorithm on the example. Watch the indegrees drop to zero one layer at a time.

Start: indegree 0 is course 0

Take 0, answer = 0

Drop indegree of 1 and 2 to 0

Take 1, answer = 0 1

Take 2, answer = 0 1 2

Drop indegree of 3 to 0

Take 3, answer = 0 1 2 3

Queue empty, all placed

Steps to Solve

  1. Build an adjacency list. For each rule [a, b], record that b points to a.
  2. Count the indegree of every course, which is how many rules point into it.
  3. Put every course with indegree 0 into a queue.
  4. Pop a course from the queue and add it to the answer list.
  5. For each course that depended on the popped one, lower its indegree by one. If it reaches 0, push it into the queue.
  6. When the queue is empty, if the answer holds every course, return it. Otherwise return an empty list.

This Python version uses a list of lists for the graph and deque for a fast queue.

course_schedule_ii.py
from collections import deque




def course_schedule(num_courses, prerequisites):
    adj = [[] for _ in range(num_courses)]   # b -> courses that need b
    indegree = [0] * num_courses             # requirements per course


    for a, b in prerequisites:               # a needs b first
        adj[b].append(a)                     # b points to a
        indegree[a] += 1                     # a gains one requirement


    queue = deque(i for i in range(num_courses) if indegree[i] == 0)


    result = []
    while queue:
        course = queue.popleft()             # take a ready course
        result.append(course)
        for nxt in adj[course]:
            indegree[nxt] -= 1               # one requirement is done
            if indegree[nxt] == 0:
                queue.append(nxt)            # now ready


    if len(result) != num_courses:
        return []                            # a cycle blocked some courses
    return result




num_courses = 4
prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
print(course_schedule(num_courses, prerequisites))

The output of the above code will be:

[0, 1, 2, 3]

Let us walk through the Python version line by line, because the logic is the heart of the whole problem.

adj = [[] for _ in range(num_courses)] builds an empty list for every course. We use this to record who depends on whom. We make a fresh list per course so each one has its own neighbor list.

indegree = [0] * num_courses starts every count at zero. The indegree of a course is how many other courses must finish before it.

for a, b in prerequisites: reads each rule. The rule [a, b] means a needs b first. So adj[b].append(a) records that finishing b unlocks a. And indegree[a] += 1 says a now has one more requirement.

queue = deque(i for i in range(num_courses) if indegree[i] == 0) collects every course that needs nothing. These are the courses we can take right away.

Inside the loop, course = queue.popleft() takes the next ready course. We add it to result because it is safe to take now. Then for each nxt that depended on it, indegree[nxt] -= 1 removes one requirement, since course is now done. When a count hits zero, that course is freshly ready, so we push it into the queue.

if len(result) != num_courses: return [] is the cycle check. If we could not place every course, the leftover ones formed a loop. A loop has no valid order, so we return an empty list.

⏱️ Time and Space Complexity

We touch every course once and every rule once. So the time is O(V + E), where V is the number of courses and E is the number of rules. The space is also O(V + E), because the adjacency list holds every rule and the queue and indegree arrays hold every course. The DFS version has the same big-O cost. Kahn’s algorithm just makes the cycle check easier, since a leftover course means a loop.

Approach Time Complexity Space Complexity
DFS topological sort (alternative) O(V + E) O(V + E)
Kahn’s BFS topological sort (best) O(V + E) O(V + E)

Tip

If the interviewer only asks “can all courses be finished” instead of the order, the same Kahn’s algorithm answers it. You just check whether the count of placed courses equals the number of courses.

🧩 Key Takeaways

  • ✅ This is a topological sort. You line up nodes so every arrow points forward.
  • ✅ Indegree is the count of requirements pointing into a course. Start with the zeros.
  • ✅ Kahn’s algorithm peels off ready courses one layer at a time using a queue.
  • ✅ If you cannot place every course, the leftovers formed a cycle, so return an empty list.
  • ✅ Both DFS and Kahn’s run in O(V + E), but Kahn’s makes the cycle check simple.

Check Your Knowledge

 4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    What does the indegree of a course mean?

    Why: Indegree is the number of prerequisites pointing into a course. A zero indegree means it is ready to take.

  2. 2

    In Kahn's algorithm, which courses go into the queue first?

    Why: Courses with indegree 0 need nothing first, so they are ready and start the process.

  3. 3

    How do you detect a cycle with Kahn's algorithm?

    Why: If some courses are never placed, they were stuck in a circular dependency, so the answer is shorter than expected.

  4. 4

    What is the time complexity of the topological sort?

    Why: We visit every course and every prerequisite edge once, giving O(V + E) time.

Score: 0 / 4

🚀 What’s Next?

Previous Walls and Gates Next Redundant Connection