Course Schedule II - Practice Coding Problems

Course Schedule II - Problem

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1.

You are given an array prerequisites where prerequisites[i] = [a_i, b_i] indicates that you must take course b_i first if you want to take course a_i.

For example, the pair [0, 1] indicates that to take course 0 you have to first take course 1.

Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Input & Output

Example 1 — Linear Chain

$ Input: numCourses = 2, prerequisites = [[1,0]]

› Output: [0,1]

💡 Note: To take course 1, you must first take course 0. So the correct order is [0,1].

Example 2 — Multiple Prerequisites

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

› Output: [0,1,2,3] or [0,2,1,3]

💡 Note: Course 0 has no prerequisites, courses 1 and 2 depend on 0, course 3 depends on both 1 and 2. Valid orderings include [0,1,2,3] or [0,2,1,3].

Example 3 — Impossible Case

$ Input: numCourses = 2, prerequisites = [[1,0],[0,1]]

› Output: []

💡 Note: Course 1 depends on 0, and course 0 depends on 1, creating a cycle. No valid ordering exists.

Constraints

1 ≤ numCourses ≤ 2000
0 ≤ prerequisites.length ≤ numCourses × (numCourses - 1)
prerequisites[i].length == 2
0 ≤ a_i, b_i < numCourses
a_i ≠ b_i
All the pairs [a_i, b_i] are distinct

Visualization

Tap to expand

Understanding the Visualization

Input

Courses 0-3 with prerequisite relationships

Build Graph

Create directed graph from prerequisites

Topological Sort

Find valid ordering respecting all dependencies

Key Takeaway

🎯 Key Insight: Transform course prerequisites into a directed graph and use topological sorting to find a valid ordering

Asked in

f Facebook 45 G Google 38 a Amazon 32 M Microsoft 28

The key insight is recognizing this as a topological sorting problem on a directed graph. We need to find an ordering where all prerequisites come before their dependent courses. Kahn's Algorithm (BFS) is optimal: build a graph, track in-degrees, process nodes with zero in-degree, and detect cycles. Time: O(V + E), Space: O(V + E).

Common Approaches

Approach	Time	Space	Notes
✓ BFS with Kahn's Algorithm	O(V + E)	O(V + E)	Use breadth-first search with in-degree counting for topological sorting
DFS with Topological Sort	O(V + E)	O(V + E)	Use depth-first search to detect cycles and build topological ordering
Brute Force - Try All Permutations	O(n! × n × p)	O(n)	Generate all possible course orderings and check which one satisfies prerequisites

BFS with Kahn's Algorithm — Algorithm Steps

Build adjacency list and calculate in-degrees
Add all courses with in-degree 0 to queue
Process queue: add course to result and decrease neighbors' in-degrees
Add newly zero in-degree courses to queue
If result contains all courses, return it; otherwise cycle exists

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate In-degrees

Count prerequisites for each course

Process Zero In-degree

Start with courses having no prerequisites

Update Neighbors

Decrease in-degrees and add newly ready courses

Code -

solution.c — C

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

int* solution(int numCourses, int prerequisites[][2], int prereqSize, int* returnSize) {
    *returnSize = 0;
    if (numCourses == 0) return NULL;
    
    // Build adjacency list using dynamic arrays
    int** graph = (int**)malloc(numCourses * sizeof(int*));
    int* graphSize = (int*)calloc(numCourses, sizeof(int));
    int* inDegree = (int*)calloc(numCourses, sizeof(int));
    
    // Initialize graph
    for (int i = 0; i < numCourses; i++) {
        graph[i] = (int*)malloc(numCourses * sizeof(int));
    }
    
    // Build graph and calculate in-degrees
    for (int i = 0; i < prereqSize; i++) {
        int course = prerequisites[i][0];
        int prereq = prerequisites[i][1];
        graph[prereq][graphSize[prereq]++] = course;
        inDegree[course]++;
    }
    
    // BFS queue
    int* queue = (int*)malloc(numCourses * sizeof(int));
    int front = 0, rear = 0;
    
    // Add courses with no prerequisites to queue
    for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0) {
            queue[rear++] = i;
        }
    }
    
    int* result = (int*)malloc(numCourses * sizeof(int));
    
    while (front < rear) {
        int current = queue[front++];
        result[(*returnSize)++] = current;
        
        // Process all courses that depend on current
        for (int i = 0; i < graphSize[current]; i++) {
            int neighbor = graph[current][i];
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0) {
                queue[rear++] = neighbor;
            }
        }
    }
    
    // Clean up
    for (int i = 0; i < numCourses; i++) {
        free(graph[i]);
    }
    free(graph);
    free(graphSize);
    free(inDegree);
    free(queue);
    
    // If we didn't process all courses, cycle exists
    if (*returnSize != numCourses) {
        free(result);
        *returnSize = 0;
        return NULL;
    }
    
    return result;
}

int main() {
    int numCourses;
    scanf("%d", &numCourses);
    
    char line[10000];
    scanf(" %[^\n]", line);
    
    int prerequisites[2000][2];
    int prereqSize = 0;
    
    if (strcmp(line, "[]") != 0) {
        char* ptr = line + 1;
        while (*ptr && *ptr != ']') {
            if (*ptr == '[') {
                ptr++;
                prerequisites[prereqSize][0] = atoi(ptr);
                while (*ptr && *ptr != ',') ptr++;
                ptr++;
                prerequisites[prereqSize][1] = atoi(ptr);
                while (*ptr && *ptr != ']') ptr++;
                prereqSize++;
            }
            ptr++;
        }
    }
    
    int returnSize;
    int* result = solution(numCourses, prerequisites, prereqSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    if (result) free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(V + E)

Visit each course once and each prerequisite edge once

✓ Linear Growth

Space Complexity

O(V + E)

Adjacency list, in-degree array, and BFS queue storage

✓ Linear Space

89.0K Views

High Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

BFS with Kahn's Algorithm — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler