Course Schedule 2 - Task Ordering Using Topological Sort

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

C++

Python

Java

Rust

Kotlin

Swift

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

int graph[MAX][MAX], indegree[MAX], queue[MAX];
int front = 0, rear = -1;

void enqueue(int v) { queue[++rear] = v; }
int dequeue() { return queue[front++]; }

void topologicalSort(int numTasks, int prerequisites[][2], int prereqSize) {
    for (int i = 0; i < prereqSize; i++) {
        int a = prerequisites[i][0];
        int b = prerequisites[i][1];
        graph[b][a] = 1;
        indegree[a]++;
    }
    
    for (int i = 0; i < numTasks; i++)
        if (indegree[i] == 0)
            enqueue(i);

    int count = 0;
    while (front <= rear) {
        int curr = dequeue();
        printf("%d ", curr);
        count++;
        for (int i = 0; i < numTasks; i++) {
            if (graph[curr][i] && --indegree[i] == 0)
                enqueue(i);
        }
    }

    if (count != numTasks)
        printf("\nCycle detected. No valid ordering.\n");
}

int main() {
    int prerequisites1[][2] = {{1,0},{2,0},{3,1},{3,2}};
    topologicalSort(4, prerequisites1, 4);
    printf("\n");
    int prerequisites2[][2] = {{0,1},{1,0}};
    topologicalSort(2, prerequisites2, 2);
    return 0;
}

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)).

About the author

Mallikarjuna Mallisetty

General programming

Mallikarjuna shares practical programming tutorials and foundational concepts designed to help developers learn by building and experimenting.

View LinkedIn profile ↗

⬅ Previous TopicCourse Schedule - Task Ordering with Prerequisites

Next Topic ⮕Find Eventual Safe States in a Directed Graph

Course Schedule 2 Using Topological Sort - Visualization