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're given numCourses representing total courses labeled from 0 to numCourses - 1, and an array prerequisites where each pair [a, b] means b must be taken before a. Your task is to return a possible ordering of courses, such that all prerequisites are met. If there's no way to complete all courses (i.e., there's a cycle), return an empty array.

Graph Representation

We represent this problem as a Directed Graph. Each course is a node, and an edge from course b to course a represents the dependency that b must be taken before a.

Using Kahn’s Algorithm (BFS-Based Topological Sort)

We create an adjacency list to store which courses depend on others. Alongside, we maintain an indegree array to count how many prerequisites each course has.

Queue Initialization

We add all courses with zero prerequisites to a queue — they can be taken immediately. Then, we process each course in the queue, and for each dependent course, we reduce its indegree (one less prerequisite). If a course’s indegree becomes 0, it gets added to the queue as it's now ready to be taken.

Cycle Detection

If at the end, we’ve added all numCourses to our result list, we have a valid order. If not, there must be a cycle — making it impossible to finish all courses. In this case, we return an empty array.

Edge Cases

No prerequisites: All courses can be taken in any order. The result will be any permutation of [0, 1, ..., numCourses - 1].
Cycle present: Like [[1, 0], [0, 1]]. It’s impossible to finish all courses; return [].
Multiple independent chains: Like [[1, 0], [3, 2]]. Each chain can be taken independently, and order between chains can vary.

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