DSA sheet · Graphs · Topological sort pattern

Course Schedule II

This is a small variation of Course Schedule, and the teacher says that problem is the prerequisite for this video. Last time we only answered "can all courses be finished?". Now we must return the order in which to take them. That order is a topological order. The code is almost identical: where we used to count each popped course, we now write it down. She also shows a tempting but wrong way to detect failure, and why we must compare against numCourses.

Every problem below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Kahn's algorithm, recording the order (the teacher's solution)
• Part B · Extra: the DFS way (reverse finishing order)
• Part C · Revision page

Part 0 · Before starting

Graph basics for this page

• Nodes are courses 0…n−1. A directed edge (b)→(a) means "b must come before a". There are no weights. (Undirected edges, drawn (a)—(b), go both ways. They aren't used here.)
• The input is an edge list of pairs [a, b] = "a needs b". We turn it into an adjacency list graph[b] = [a, …] ("who is waiting for b?"). Course ids are 0…n−1, so a list of lists is enough, and we don't need a dictionary.
• Indegree of a course = the number of arrows coming into it = how many of its prerequisites are still unfinished. Indegree 0 means it can be taken now.
• Visited: usually an array that stops us from handling a node twice. In Kahn's algorithm, the moment the indegree drops to 0 already happens only once, so it works as our visited signal.
• BFS uses a queue (collections.deque), and DFS uses recursion. Graphs can be in several separate pieces (connected components), so we start from every free course, not just course 0.

numCourses = 3
prerequisites = [[1, 0], [2, 1]]       # 1 needs 0, 2 needs 1
graph = [[] for _ in range(numCourses)]
indegree = [0] * numCourses
for course, pre in prerequisites:
    graph[pre].append(course)          # pre -> course
    indegree[course] += 1
print(graph)                           # [[1], [2], []]
print(indegree)                        # [0, 1, 1]

Topological order

A topological order lists every node so that each arrow points forward: for every edge b → a, b appears before a. It's exactly a valid timetable of courses. It exists only when there is no cycle. In a cycle every course waits for another one in the same cycle, so none of them can be placed first. A graph can have more than one valid order, and LeetCode accepts any of them.

Part A · Kahn's algorithm, recording the order

LeetCode 210 · Medium

1The question in simple words

The same setup as Course Schedule: numCourses courses, and pairs [a, b] meaning "take b before a". This time, return a list of all courses in an order you could take them. If it's impossible (there's a cycle), return an empty list [].

• n = 2, [[1,0]] → [0, 1].
• n = 4, [[1,0],[2,0],[3,1],[3,2]] → [0, 1, 2, 3] or [0, 2, 1, 3]. Both are correct.
• n = 1, [] → [0].

The teacher reuses her 5-course example: [[1,0],[0,2],[2,3],[2,4],[3,4]].

 (4) ──→ (3)
  │       │
  ↓       │
 (2) ←────┘
  │
  ↓
 (0) ──→ (1)

graph = {0:[1], 1:[], 2:[0], 3:[2], 4:[2, 3]}, and indegree for courses [0, 1, 2, 3, 4] = [1, 1, 2, 1, 0].

2What the constraints tell us

• 1 ≤ numCourses ≤ 2000 → at least one course, so a successful answer is never empty. An empty answer can only mean "impossible".
• 0 ≤ prerequisites.length ≤ numCourses × (numCourses − 1) → E can be large in theory (millions), but O(V + E) is still fine. With no pairs at all, any order works.
• All pairs are distinct, and a != b (no course needs itself).
• The answer list has exactly n numbers, so the extra space for the output is O(V).

3Intuition: write down courses in the order you take them

In Course Schedule we already took the courses one by one: each pop from the queue was "I take this course now". That sequence of pops is a valid order, because a course only enters the queue after everything it needs has been popped earlier.

So the only change: instead of count += 1, append the course to order. At the end, if all n courses made it into order, return it. Otherwise return [].

4Building the logic, and the trap she shows

Recording the order

In Java she makes an int array of size n plus an index pointer starting at 0. Each pop does order[index] = course; index++. In Python we just keep a list and append. Then len(order) plays the role of her index.

How do we know it failed?

Fully stuck (her first cycle example): [[0,1],[1,0]]. Both indegrees are 1, nothing has indegree 0, the queue starts empty, the loop never runs, and order stays empty. So "index is still 0" means failure here.

That gives a tempting rule: "if at least one course was taken (index > 0), return the order". She shows why it's wrong:

n = 4, [[0,1],[1,2],[2,1],[1,3]]: 0 needs 1, 1 needs 2 and 3, 2 needs 1.

 (3) ──→ (1) ──→ (0)
          ↑ │
          │ ↓
          (2)        cycle 1 ⇄ 2

indegree = [1, 2, 1, 0]. Queue = [3]. Pop 3 → order = [3]. Lower 1: 2 → 1. Not 0. The queue is empty, so we stop with order = [3]. The index is 1, which is > 0, but we took only 1 of 4 courses. Courses 1 and 2 wait for each other, and 0 waits behind them.

5Approach steps

1. Build graph (pre → course) and indegree.
2. Push every course with indegree 0 into the queue.
3. While the queue isn't empty: pop a course and append it to order.
4. For each child: lower its indegree. If it reaches 0, push it.
5. If len(order) == numCourses, return order. Otherwise return [].

6Code (Python)

from collections import deque

class Solution:
    def findOrder(self, numCourses, prerequisites):
        graph = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses
        for course, pre in prerequisites:
            graph[pre].append(course)
            indegree[course] += 1

        queue = deque()
        for i in range(numCourses):
            if indegree[i] == 0:
                queue.append(i)

        order = []                                 # was "count" in Course Schedule
        while queue:
            course = queue.popleft()
            order.append(course)                   # was "count += 1"
            for child in graph[course]:
                indegree[child] -= 1
                if indegree[child] == 0:
                    queue.append(child)

        if len(order) == numCourses:               # every course was taken
            return order
        return []                                  # a cycle blocked some courses

7Code line by line (what changed from Course Schedule)

8Dry run: indegree, queue and order after every step

Her 5-course example. graph = {0:[1], 1:[], 2:[0], 3:[2], 4:[2, 3]}.

Check the arrows: 4→3 (4 before 3 ✓), 4→2 ✓, 3→2 ✓, 2→0 ✓, 0→1 ✓.

The trap example, step by step

n = 4, [[0,1],[1,2],[2,1],[1,3]] → graph = {1:[0, 2], 2:[1], 3:[1], 0:[]}.

 (3✓) ──→ (1:1) ──→ (0:1)
           ↑ │
           │ ↓
           (2:1)

 (0:1) ──→ (1:1)
   ↑          │
   └──────────┘
 queue starts empty → []

9Complexity & remember

• Time O(V + E): the same as Course Schedule. Each course is pushed and popped at most once, and each edge lowers one indegree once.
• Space O(V + E): the graph (V lists, E entries), the indegree array and the queue. The order list adds O(V), and she points out that this is the space the answer itself needs.

Part B · Extra: the DFS way (reverse finishing order)

Not in this video. It continues the DFS homework from Course Schedule, because interviewers often ask for both.

1The question

The same: return a valid order, or [] if there's a cycle.

2What the constraints tell us

Up to 2000 courses in a chain → recursion up to 2000 deep, which is more than Python's default limit of ~1000. Raise it with sys.setrecursionlimit.

3Intuition: a course finishes after everything that depends on it

Run DFS along the arrows pre → course. A DFS call on course u finishes only after it has finished every course reachable from u, i.e. every course that needs u, directly or indirectly. So if we write u down at the moment it finishes, u lands after all the courses that need it. Reverse that list and u comes before all of them, which is exactly a topological order.

At the same time we detect cycles with the 3-state marker from Course Schedule (Part C): 0 = new, 1 = on the current path, 2 = done. An arrow into a state-1 course is a cycle → return [].

4Building the logic

• dfs(u): set state 1. For each child: state 1 → cycle. State 0 → recurse. State 2 → skip.
• When all children are done: set state 2 and append u to post (the finishing order).
• Start a DFS from every course still in state 0 (to cover separate pieces).
• The answer is post reversed.

5Approach steps

1. Build the graph. Set state = [0] * n and post = [].
2. For each course in state 0: run dfs. If it found a cycle, return [].
3. Return post[::-1].

6Code (Python)

import sys

class Solution:
    def findOrder(self, numCourses, prerequisites):
        sys.setrecursionlimit(10000)
        graph = [[] for _ in range(numCourses)]
        for course, pre in prerequisites:
            graph[pre].append(course)

        state = [0] * numCourses       # 0 = new, 1 = on current path, 2 = done
        post = []                      # courses in the order their DFS finishes

        def dfs(u):                    # False means a cycle was found
            state[u] = 1
            for v in graph[u]:
                if state[v] == 1:
                    return False
                if state[v] == 0 and not dfs(v):
                    return False
            state[u] = 2
            post.append(u)             # everything that needs u is already in post
            return True

        for c in range(numCourses):
            if state[c] == 0 and not dfs(c):
                return []
        return post[::-1]

7Code line by line

8Dry run (5-course example)

1. c = 0: dfs(0) → child 1 → dfs(1) has no children → post = [1]. Back in 0 → post = [1, 0].
2. c = 1: already done.
3. c = 2: dfs(2) → child 0 is done → post = [1, 0, 2].
4. c = 3: dfs(3) → child 2 is done → post = [1, 0, 2, 3].
5. c = 4: dfs(4) → children 2 and 3 are done → post = [1, 0, 2, 3, 4].
6. Reversed: [4, 3, 2, 0, 1], the same order as Kahn's gave.

On the trap example, dfs(1) → dfs(2) sees course 1 in state 1 → cycle → [].

9Complexity & remember

• Time O(V + E) and Space O(V + E) (graph, state, post, recursion stack).

Part C · Revision page

s = Solution()
print(s.findOrder(2, [[1, 0]]))                                   # [0, 1]
print(s.findOrder(5, [[1, 0], [0, 2], [2, 3], [2, 4], [3, 4]]))   # [4, 3, 2, 0, 1]
print(s.findOrder(4, [[1, 0], [2, 0], [3, 1], [3, 2]]) in ([0, 1, 2, 3], [0, 2, 1, 3]))  # True
print(s.findOrder(2, [[1, 0], [0, 1]]))                           # []
print(s.findOrder(4, [[0, 1], [1, 2], [2, 1], [1, 3]]))           # []
print(s.findOrder(1, []))                                         # [0]

Based on this video: Course Schedule II | Graph · Topological Sort