Course Schedule - Practice Coding Problems

Course Schedule - 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 true if you can finish all courses. Otherwise, return false.

Input & Output

Example 1 — Basic Valid Case

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

› Output: true

💡 Note: Course 1 requires course 0 first. Valid order: take course 0, then course 1. No circular dependency.

Example 2 — Circular Dependency

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

› Output: false

💡 Note: Course 1 requires course 0, but course 0 requires course 1. This creates a cycle, making it impossible to complete all courses.

Example 3 — No Prerequisites

$ Input: numCourses = 3, prerequisites = []

› Output: true

💡 Note: No prerequisites means all courses can be taken in any order. Always possible to complete.

Constraints

1 ≤ numCourses ≤ 10⁵
0 ≤ prerequisites.length ≤ 5000
prerequisites[i].length == 2
0 ≤ a_i, b_i < numCourses

Visualization

Tap to expand

Understanding the Visualization

Input

numCourses=2, prerequisites=[[1,0]] - course 1 needs course 0

Process

Build graph and check for cycles using DFS or topological sort

Output

Return true if no cycles (can complete), false if cycles exist

Key Takeaway

🎯 Key Insight: Course scheduling is cycle detection in a directed graph - cycles make completion impossible

Asked in

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

The key insight is that this is a cycle detection problem in a directed graph. If there's a cycle in the prerequisite dependencies, it's impossible to complete all courses. The optimal approach uses DFS with three states (unvisited, visiting, visited) to detect back edges indicating cycles. Time: O(V+E), Space: O(V+E).

Common Approaches

Approach	Time	Space	Notes
✓ DFS Cycle Detection	O(V + E)	O(V + E)	Use depth-first search to detect cycles in the prerequisite graph
BFS Topological Sort (Kahn's Algorithm)	O(V + E)	O(V + E)	Use BFS to perform topological sorting by tracking in-degrees
Brute Force - Try All Orderings	O(n! × n²)	O(n)	Generate all possible course orderings and check if any satisfies prerequisites

DFS Cycle Detection — Algorithm Steps

Build adjacency list from prerequisites
For each unvisited course, start DFS
Use three states to track visit status and detect back edges
Return false if cycle found, true otherwise

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Graph

Create adjacency list from prerequisites

DFS with States

Use unvisited(0), visiting(1), visited(2) states

Detect Cycles

Back edge to visiting node indicates cycle

Code -

solution.c — C

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

typedef struct {
    int* data;
    int size;
    int capacity;
} IntList;

IntList* createList() {
    IntList* list = (IntList*)malloc(sizeof(IntList));
    list->data = (int*)malloc(10 * sizeof(int));
    list->size = 0;
    list->capacity = 10;
    return list;
}

void addToList(IntList* list, int val) {
    if (list->size >= list->capacity) {
        list->capacity *= 2;
        list->data = (int*)realloc(list->data, list->capacity * sizeof(int));
    }
    list->data[list->size++] = val;
}

bool dfs(int course, IntList** graph, int* state) {
    if (state[course] == 1) return false; // Cycle detected
    if (state[course] == 2) return true;  // Already processed
    
    state[course] = 1; // Mark as visiting
    
    for (int i = 0; i < graph[course]->size; i++) {
        int neighbor = graph[course]->data[i];
        if (!dfs(neighbor, graph, state)) {
            return false;
        }
    }
    
    state[course] = 2; // Mark as visited
    return true;
}

bool solution(int numCourses, int prerequisites[][2], int prereqSize) {
    // Build adjacency list
    IntList** graph = (IntList**)malloc(numCourses * sizeof(IntList*));
    for (int i = 0; i < numCourses; i++) {
        graph[i] = createList();
    }
    
    for (int i = 0; i < prereqSize; i++) {
        addToList(graph[prerequisites[i][1]], prerequisites[i][0]);
    }
    
    // 0: unvisited, 1: visiting, 2: visited
    int* state = (int*)calloc(numCourses, sizeof(int));
    
    bool result = true;
    for (int i = 0; i < numCourses; i++) {
        if (state[i] == 0) {
            if (!dfs(i, graph, state)) {
                result = false;
                break;
            }
        }
    }
    
    // Cleanup
    for (int i = 0; i < numCourses; i++) {
        free(graph[i]->data);
        free(graph[i]);
    }
    free(graph);
    free(state);
    
    return result;
}

int main() {
    int numCourses;
    scanf("%d", &numCourses);
    
    char line[10000];
    scanf(" %[^\n]", line);
    
    int prerequisites[1000][2];
    int prereqSize = 0;
    
    if (strcmp(line, "[]") != 0) {
        char* ptr = line + 1;
        while (*ptr && *ptr != ']') {
            if (*ptr == '[') {
                ptr++;
                int a = 0, b = 0;
                while (*ptr >= '0' && *ptr <= '9') {
                    a = a * 10 + (*ptr - '0');
                    ptr++;
                }
                ptr++; // Skip comma
                while (*ptr >= '0' && *ptr <= '9') {
                    b = b * 10 + (*ptr - '0');
                    ptr++;
                }
                prerequisites[prereqSize][0] = a;
                prerequisites[prereqSize][1] = b;
                prereqSize++;
                ptr++; // Skip ]
            } else {
                ptr++;
            }
        }
    }
    
    bool result = solution(numCourses, prerequisites, prereqSize);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(V + E)

Visit each vertex and edge once, where V=numCourses, E=prerequisites

✓ Linear Growth

Space Complexity

O(V + E)

Adjacency list storage plus recursion stack depth up to V

✓ Linear Space

67.5K Views

High Frequency

~25 min Avg. Time

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

DFS Cycle Detection — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler