Course Schedule II

Problem Description

There are a total of numCourses courses labeled from 0 to numCourses - 1. Given prerequisites as pairs [ai, bi] (indicating that course bi must be taken before course ai), return an ordering of courses ensuring that all prerequisites are satisfied. If no such ordering exists (due to a cycle), return an empty array.

Key Insights

• This is a topological sort problem on a directed graph.
• The courses are nodes, and prerequisites form directed edges.
• We can solve the problem by either:
  • Using DFS with cycle detection and a stack for topological ordering.
  • Using BFS (Kahn's Algorithm) to process nodes with zero in-degrees.
• If at any point no node with a zero in-degree is available, a cycle exists and no valid order can be produced.

Space and Time Complexity

Time Complexity: O(V + E) where V is the number of courses and E is the number of prerequisite pairs. Space Complexity: O(V + E) for storing the graph and in-degree array.

Solution

We treat the problem as a topological sort on a directed acyclic graph (DAG). For a BFS approach using Kahn’s algorithm:

1. Build an adjacency list for the graph and an in-degree array to record the number of prerequisites (incoming edges) for each course.
2. Initialize a queue with all courses that have an in-degree of zero (i.e., courses that can be taken without prerequisites).
3. Dequeue nodes from the queue, add them to the ordering, and reduce the in-degree of their neighbors.
4. If a neighbor’s in-degree becomes zero, add it to the queue.
5. If the final ordering includes all courses, return the ordering; otherwise, return an empty array indicating a cycle. The chosen data structures are:

• A list (or array) for the in-degree counts.
• A dictionary (or array of lists) for the adjacency list.
• A queue to process nodes with zero in-degree.

Code Solutions