Course Schedule 2 Using Topological Sort (Graphs)

Problem Statement❯

There are N tasks, labeled from 0 to N-1. Some tasks have prerequisites, meaning a task must be done only after another task is completed. These dependencies are given as pairs [a, b] meaning b must be done before a.

The goal is to return an ordering of tasks that satisfies all the prerequisites. If no valid ordering exists (due to a cycle), return an empty array.

This is a classic case of Topological Sorting in a Directed Graph.

Examples❯

N	Prerequisites	Output	Description
2	[[1, 0]]	[0, 1]	0 before 1
4	[[1, 0], [2, 0], [3, 1], [3, 2]]	[0, 1, 2, 3] or [0, 2, 1, 3]	Multiple valid orderings exist
1	[]	[0]	Only one task, no prerequisites
2	[[0, 1], [1, 0]]	[]	Circular dependency, no valid order
3	[]	[0, 1, 2]	No dependencies, any order is valid

Solution❯

Understanding the Problem

You are given an integer numCourses, which represents the total number of courses labeled from 0 to numCourses - 1. You are also given a list of prerequisite pairs prerequisites, where each pair [a, b] means that you must complete course b before course a.

Your goal is to determine a valid order to take all the courses, such that the prerequisites are respected. If there’s no way to complete all courses due to circular dependencies (cycles), you should return an empty array.

Step-by-Step Solution with Example

Step 1: Represent the problem as a directed graph

Each course is a node. Each prerequisite pair [a, b] becomes a directed edge from b → a. This means course b must come before a.

Step 2: Build the adjacency list and indegree array

The adjacency list keeps track of all courses that depend on a course. The indegree array counts how many prerequisites each course has.

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

Adjacency List:
0 → [1, 2]
1 → [3]
2 → [3]

Indegree:
[0, 1, 1, 2]

Step 3: Initialize the queue with courses that have zero prerequisites

We can start with courses that have indegree 0 because they don’t depend on any other course.

In this example, course 0 has no prerequisites, so we begin with queue = [0].

Step 4: Perform topological sort using Kahn’s Algorithm

We repeat the following:

Pop a course from the queue
Add it to the result list
Reduce the indegree of all its neighbors
If any neighbor’s indegree becomes 0, add it to the queue

Process:
queue = [0]         → result = []
take 0              → result = [0]
decrease indegree of 1 → indegree[1] = 0 → add 1 to queue
decrease indegree of 2 → indegree[2] = 0 → add 2 to queue

queue = [1, 2]
take 1              → result = [0, 1]
decrease indegree of 3 → indegree[3] = 1

take 2              → result = [0, 1, 2]
decrease indegree of 3 → indegree[3] = 0 → add 3 to queue

take 3              → result = [0, 1, 2, 3]

Step 5: Verify result length

If the result contains all numCourses (i.e., length equals numCourses), we have found a valid order. If not, it means there was a cycle.

Edge Cases

No prerequisites: If the list is empty, all courses can be taken in any order. For example, numCourses = 3, prerequisites = [] → possible result: [0, 1, 2].
Cycle in prerequisites: Example [[1, 0], [0, 1]] forms a cycle. No course order is valid. Return [].
Disconnected components: Example [[1, 0], [3, 2]]. These are independent chains and can be solved separately. Valid result: [0, 1, 2, 3] or [2, 3, 0, 1].

Finally

This problem is a classic example of topological sorting in a directed graph. Kahn’s Algorithm is an efficient way to build the course order using a queue and indegree tracking. Always ensure to handle cycles and special cases like no prerequisites or disconnected graphs.

Practicing this problem strengthens your understanding of graph algorithms and helps you apply them in scheduling and dependency resolution scenarios.

Algorithm Steps❯

Initialize an adjacency list graph and an array indegree to count prerequisites for each node.
Fill the graph and indegree based on given prerequisites.
Initialize a queue with nodes having indegree = 0.
While the queue is not empty:

Pop a node from the queue and add it to the result list.
For each neighbor, decrement its indegree.
If indegree becomes 0, enqueue the neighbor.

If the result list contains all tasks, return it. Otherwise, return an empty array.

Code

JavaScript

function findOrder(numCourses, prerequisites) {
  const graph = Array.from({ length: numCourses }, () => []);
  const indegree = Array(numCourses).fill(0);

  for (const [a, b] of prerequisites) {
    graph[b].push(a);
    indegree[a]++;
  }

  const queue = [];
  for (let i = 0; i < numCourses; i++) {
    if (indegree[i] === 0) queue.push(i);
  }

  const result = [];
  while (queue.length > 0) {
    const course = queue.shift();
    result.push(course);
    for (const neighbor of graph[course]) {
      indegree[neighbor]--;
      if (indegree[neighbor] === 0) queue.push(neighbor);
    }
  }

  return result.length === numCourses ? result : [];
}

console.log(findOrder(4, [[1,0],[2,0],[3,1],[3,2]])); // [0,1,2,3] or [0,2,1,3]
console.log(findOrder(2, [[0,1],[1,0]])); // [] due to cycle

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(V + E)	In the best case, we visit all vertices and edges once — one pass for building the graph and one pass for processing the queue.
Average Case	O(V + E)	Regardless of prerequisites distribution, all vertices and edges are still processed once each.
Worst Case	O(V + E)	Even with dense dependencies or cycles, we process each vertex and edge exactly once in topological sort.

Space Complexity❯

O(V + E)

Explanation: We use space for the adjacency list (O(E)), the indegree array (O(V)), the queue (up to O(V)), and the result list (O(V)).

⬅ Previous TopicCourse Schedule - Task Ordering with Prerequisites

Next Topic ⮕Find Eventual Safe States in a Directed Graph

Comments

Loading comments...