# LeetCode 210: Course Schedule II

## Problem Restatement

We are given:

```python
numCourses
prerequisites
```

Each prerequisite pair:

```python
[a, b]
```

means:

```text
to take course a, you must first complete course b
```

We must return a valid order in which all courses can be completed.

If it is impossible because of a cycle, return an empty list.

The official statement says: return any valid ordering of courses that allows completion of all courses. If no ordering exists, return an empty array.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Integer `numCourses` and prerequisite pairs |
| Output | A valid course ordering |
| Return `[]` | No valid ordering exists |
| Graph type | Directed graph |
| Core problem | Topological sorting |

Example function shape:

```python
def findOrder(numCourses: int, prerequisites: list[list[int]]) -> list[int]:
    ...
```

## Examples

Example 1:

```python
numCourses = 2
prerequisites = [[1,0]]
```

Graph:

```text
0 -> 1
```

Take `0` first, then `1`.

Valid answer:

```python
[0, 1]
```

Example 2:

```python
numCourses = 4
prerequisites = [[1,0],[2,0],[3,1],[3,2]]
```

Graph:

```text
0 -> 1
0 -> 2
1 -> 3
2 -> 3
```

Possible valid orders:

```python
[0,1,2,3]
```

or:

```python
[0,2,1,3]
```

Both are correct.

Example 3:

```python
numCourses = 2
prerequisites = [[1,0],[0,1]]
```

Graph:

```text
0 -> 1
1 -> 0
```

This creates a cycle.

No valid ordering exists.

Answer:

```python
[]
```

## Relationship to LeetCode 207

LeetCode 207 asked:

```text
Can we finish all courses?
```

LeetCode 210 asks:

```text
What is the actual valid ordering?
```

The core idea is the same:

- detect cycles
- perform topological sorting

If the graph is acyclic, a topological order exists.

## Understanding Topological Order

A topological ordering is an ordering of nodes such that:

```text
every prerequisite appears before its dependent course
```

Example:

```text
0 -> 1
0 -> 2
1 -> 3
2 -> 3
```

A valid ordering:

```text
0, 1, 2, 3
```

because:

- `0` appears before `1`
- `0` appears before `2`
- `1` appears before `3`
- `2` appears before `3`

## Key Insight

Courses with indegree `0` have no remaining prerequisites.

So:

- they can be taken immediately
- after taking them, we remove their outgoing edges
- this may unlock more courses

This is exactly Kahn's topological sorting algorithm.

## Algorithm (BFS Topological Sort)

1. Build the graph.
2. Compute indegree of every course.
3. Push all indegree `0` courses into a queue.
4. Repeatedly:
   - pop a course
   - append it to the answer
   - reduce indegree of neighbors
   - if a neighbor becomes indegree `0`, push it into the queue
5. If all courses were processed, return the ordering.
6. Otherwise return `[]`.

## Walkthrough

Use:

```python
numCourses = 4
prerequisites = [[1,0],[2,0],[3,1],[3,2]]
```

Initial indegrees:

| Course | Indegree |
|---|---:|
| 0 | 0 |
| 1 | 1 |
| 2 | 1 |
| 3 | 2 |

Initial queue:

```text
[0]
```

Process `0`.

Order becomes:

```text
[0]
```

Reduce indegrees:

| Course | New Indegree |
|---|---:|
| 1 | 0 |
| 2 | 0 |

Push:

```text
[1, 2]
```

Process `1`.

Order:

```text
[0,1]
```

Reduce indegree of `3`:

```text
2 -> 1
```

Process `2`.

Order:

```text
[0,1,2]
```

Reduce indegree of `3`:

```text
1 -> 0
```

Push `3`.

Process `3`.

Final order:

```python
[0,1,2,3]
```

All courses processed successfully.

## Why Cycles Prevent Completion

Suppose:

```python
[[1,0],[0,1]]
```

Indegrees:

| Course | Indegree |
|---|---:|
| 0 | 1 |
| 1 | 1 |

No course has indegree `0`.

The queue starts empty.

We cannot begin.

That means no valid ordering exists.

## Correctness

The algorithm always selects courses with indegree `0`.

A course with indegree `0` has no unmet prerequisites, so placing it next in the ordering is valid.

After removing a course, the algorithm removes all outgoing edges from that course by decrementing neighbor indegrees. This correctly models completing that prerequisite.

If the graph is acyclic, there is always at least one node with indegree `0`, so the process continues until every course is added to the ordering.

If the graph contains a cycle, every node in the cycle always depends on another node in the cycle. Therefore none of them can ever reach indegree `0`.

In that case, some courses remain unprocessed, and the algorithm returns an empty list.

Thus:

- a returned ordering is always valid
- returning `[]` correctly indicates that no valid ordering exists

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(V + E)` | Every node and edge is processed once |
| Space | `O(V + E)` | Graph, indegree array, queue, and output |

Where:

- `V = numCourses`
- `E = number of prerequisite pairs`

## BFS Topological Sort Implementation

```python
from collections import deque

class Solution:
    def findOrder(self, numCourses: int, prerequisites: list[list[int]]) -> list[int]:
        graph = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses

        for course, prereq in prerequisites:
            graph[prereq].append(course)
            indegree[course] += 1

        queue = deque()

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

        order = []

        while queue:
            current = queue.popleft()
            order.append(current)

            for neighbor in graph[current]:
                indegree[neighbor] -= 1

                if indegree[neighbor] == 0:
                    queue.append(neighbor)

        if len(order) == numCourses:
            return order

        return []
```

## Code Explanation

Build adjacency list:

```python
graph = [[] for _ in range(numCourses)]
```

Track prerequisites count:

```python
indegree = [0] * numCourses
```

Build edges:

```python
graph[prereq].append(course)
indegree[course] += 1
```

Push courses with no prerequisites:

```python
if indegree[course] == 0:
    queue.append(course)
```

Process courses:

```python
current = queue.popleft()
order.append(current)
```

Reduce neighbor indegrees:

```python
indegree[neighbor] -= 1
```

When a course becomes available:

```python
if indegree[neighbor] == 0:
    queue.append(neighbor)
```

Finally:

```python
if len(order) == numCourses:
    return order
```

Otherwise a cycle exists:

```python
return []
```

## DFS Topological Sort

We can also solve the problem using DFS.

Idea:

- recursively visit dependencies
- add nodes after exploring neighbors
- reverse the final order

Cycle detection uses three states:

| State | Meaning |
|---|---|
| `0` | Unvisited |
| `1` | Currently visiting |
| `2` | Fully processed |

If DFS reaches a node already marked `1`, a cycle exists.

## DFS Implementation

```python
class Solution:
    def findOrder(self, numCourses: int, prerequisites: list[list[int]]) -> list[int]:
        graph = [[] for _ in range(numCourses)]

        for course, prereq in prerequisites:
            graph[prereq].append(course)

        state = [0] * numCourses
        order = []

        def dfs(node):
            if state[node] == 1:
                return False

            if state[node] == 2:
                return True

            state[node] = 1

            for neighbor in graph[node]:
                if not dfs(neighbor):
                    return False

            state[node] = 2
            order.append(node)

            return True

        for course in range(numCourses):
            if not dfs(course):
                return []

        return order[::-1]
```

## DFS Explanation

When entering a node:

```python
state[node] = 1
```

This marks it inside the recursion stack.

If DFS revisits another `1` node, a cycle exists.

After exploring all neighbors:

```python
state[node] = 2
```

The node is fully processed.

Append the node after exploring dependencies:

```python
order.append(node)
```

Finally reverse the result:

```python
return order[::-1]
```

because DFS postorder builds the order backward.

## Testing

```python
def is_valid_order(order, numCourses, prerequisites):
    if len(order) != numCourses:
        return False

    position = {}

    for i, course in enumerate(order):
        position[course] = i

    for course, prereq in prerequisites:
        if position[prereq] > position[course]:
            return False

    return True

def run_tests():
    s = Solution()

    order = s.findOrder(2, [[1,0]])
    assert is_valid_order(order, 2, [[1,0]])

    order = s.findOrder(4, [[1,0],[2,0],[3,1],[3,2]])
    assert is_valid_order(order, 4, [[1,0],[2,0],[3,1],[3,2]])

    assert s.findOrder(2, [[1,0],[0,1]]) == []

    order = s.findOrder(1, [])
    assert is_valid_order(order, 1, [])

    order = s.findOrder(3, [[1,0],[2,1]])
    assert is_valid_order(order, 3, [[1,0],[2,1]])

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Simple dependency | Basic valid ordering |
| Larger DAG | Multiple valid orders |
| Two-node cycle | Impossible case |
| No prerequisites | Any order works |
| Chain dependencies | Linear ordering |