⚡Flashcard Drill➔
NeetCode #576LC-210MediumGraphsNC 150NC 250
← Back to All Problems

#576 · #210 · Course Schedule II(课程表 II)

📌 Problem Statement & Constraints

There are numCourses courses and prerequisites[i] = [a, b] means b before a. Return a valid order to finish all courses, or an empty array if impossible. Constraints: 1 <= numCourses <= 2000, 0 <= prerequisites.length <= numCourses * (numCourses - 1).

💡 Core Algorithmic Approaches

  1. This is a topological sort. Kahn's algorithm produces the order directly.
  2. Start from all in-degree-zero nodes; each removal appends to the order and decrements its successors' in-degrees.
  3. If the order contains all nodes, it is valid; otherwise a cycle exists and the answer is empty.
  4. Any valid topological order is accepted, so the tie-breaking does not matter.

💻 Benchmark Python3 Implementation

class Solution:
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        from collections import defaultdict, deque
        g = defaultdict(list)
        indeg = [0] * numCourses
        for a, b in prerequisites:         # b must precede a
            g[b].append(a)
            indeg[a] += 1
        q = deque(i for i in range(numCourses) if indeg[i] == 0)
        order = []
        while q:
            node = q.popleft()
            order.append(node)
            for nxt in g[node]:
                indeg[nxt] -= 1
                if indeg[nxt] == 0:
                    q.append(nxt)
        return order if len(order) == numCourses else []

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(V + E): each node and edge is processed once.
💾 Space Complexity
O(V + E) for the graph.

⚠️ Interview Pitfalls & Follow-ups

  • Returning a partial order when a cycle exists: the length check converts it to an empty array.
  • Appending to the order when enqueuing instead of when popping: the ordering constraint would be violated.
  • Reversing the edge direction: [a, b] means b -> a.
  • Sorting the output: any valid order is accepted, and sorting could break the constraints.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems