What is the brute force approach and complexity for Course Schedule?

From each course, follow the prerequisite arrows; if the walk returns to the start, it is stuck in a loop with time complexity O(V · (V + E)) and space complexity O(V + E).

What is the optimal approach and complexity for Course Schedule?

Keep a count of unfinished prerequisites; take free courses from a queue; if every course gets taken, there is no loop with optimal time complexity O(V + E) and space complexity O(V + E).

How do you identify the pattern for Course Schedule?

Look for key signals in the prompt: "prerequisites [a, b]" indicates Each pair is an arrow: course b must come before course a. The courses form a directed graph.; "can you finish all courses?" indicates A yes or no question. It asks whether a loop exists, not for the order itself.; "courses that block each other" indicates That is a loop. A loop means the processing order can never start..

Course Schedule

Medium·LeetCode #207Basic Anchor

LeetCode

Jump:

30-Second Mental ModelTopological Sort — Kahn's algorithm, cycle check (taken == numCourses)

Complexity:O(V · (V + E))→O(V + E)

Key Insight

Take the courses in waves. A course with no unfinished prerequisites is always safe to take now. Taking it removes one arrow from every course that waited on it. If the queue runs dry before all n courses are taken, the courses left over are all waiting on each other, so there is a loop.

Core Validity Invariant

A course is safe to take exactly when its waiting count is 0: every prerequisite is already taken, so nothing blocks it.

Problem

There are numCourses courses, labelled from 0 to numCourses − 1. prerequisites[i] = [a, b] means you must finish course b before you can take course a.

Return true if you can take every course. Return false if some courses block each other, so that none of them can be taken first.

Input

numCourses, and prerequisites, a list of pairs [a, b].

Output

true if every course can be taken in some order, otherwise false.

Example 1

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

Output: true

Take course 0 first, then course 1. Nothing blocks anything.

Example 2

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

Output: false

Course 1 needs course 0, and course 0 needs course 1. Neither one can be taken first, so the schedule is impossible.

Constraints

• 1 ≤ numCourses ≤ 2000
• 0 ≤ prerequisites.length ≤ 5000
• Each prerequisites[i] has exactly 2 numbers.
• 0 ≤ aᵢ, bᵢ < numCourses
• All the pairs in prerequisites are different.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
For a pair [a, b], which course has to come first: a or b? Which way should the arrow point?
2.
If a group of courses all need each other, can any one of them be taken first?
3.
Which courses have no prerequisites at all? Could I start there?
4.
After I take a course, which other courses get closer to being free?
5.
If I manage to take every course one at a time, how many courses should I have taken at the end?

Brute force approach

Idea

A course is stuck when you can follow the "must come before" arrows from it and get back to the same course. So for each course, run a search from it. If the search reaches the course again, there is a loop and the answer is false.

Thinking process

1
The arrow for [a, b] goes from b to a, because b must come before a.
2
If the arrows from course s lead back to s, then s can never be taken first.
3
So for each course s, run a DFS from s and check whether it reaches s again.
4
Check on example 2, [[1, 0], [0, 1]]: from course 0 the arrow 0 → 1 and then 1 → 0 brings us back to 0. Course 0 is stuck, so the answer is false.

Code & Implementation

brute.cpp

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // next[b] = courses that need course b first (arrow b -> a for [a, b]).
        vector<vector<int>> next(numCourses);
        for (auto& p : prerequisites) next[p[1]].push_back(p[0]);

        // A loop exists if some course can walk back to itself.
        for (int start = 0; start < numCourses; start++) {
            vector<bool> seen(numCourses, false);
            vector<int> todo = next[start];
            while (!todo.empty()) {
                int c = todo.back();
                todo.pop_back();
                if (c == start) return false;   // came back: start is stuck in a loop
                if (seen[c]) continue;
                seen[c] = true;
                for (int d : next[c]) todo.push_back(d);
            }
        }
        return true;
    }
};

import java.util.*;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // next[b] = courses that need course b first (arrow b -> a for [a, b]).
        List<List<Integer>> next = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            next.add(new ArrayList<>());
        }
        for (int[] p : prerequisites) {
            next.get(p[1]).add(p[0]);
        }

        // A loop exists if some course can walk back to itself.
        for (int start = 0; start < numCourses; start++) {
            boolean[] seen = new boolean[numCourses];
            Deque<Integer> todo = new ArrayDeque<>(next.get(start));
            while (!todo.isEmpty()) {
                int c = todo.pop();
                if (c == start) return false;   // came back: start is stuck in a loop
                if (seen[c]) continue;
                seen[c] = true;
                for (int d : next.get(c)) {
                    todo.push(d);
                }
            }
        }
        return true;
    }
}

from typing import List

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # next[b] = courses that need course b first (arrow b -> a for [a, b]).
        next_courses: List[List[int]] = [[] for _ in range(numCourses)]
        for a, b in prerequisites:
            next_courses[b].append(a)

        # A loop exists if some course can walk back to itself.
        for start in range(numCourses):
            seen = [False] * numCourses
            todo = list(next_courses[start])
            while todo:
                c = todo.pop()
                if c == start:
                    return False   # came back: start is stuck in a loop
                if seen[c]:
                    continue
                seen[c] = True
                for d in next_courses[c]:
                    todo.append(d)

        return True

export function canFinish(numCourses: number, prerequisites: number[][]): boolean {
    // next[b] = courses that need course b first (arrow b -> a for [a, b]).
    const next: number[][] = Array.from({ length: numCourses }, () => []);
    for (const [a, b] of prerequisites) {
        next[b].push(a);
    }

    // A loop exists if some course can walk back to itself.
    for (let start = 0; start < numCourses; start++) {
        const seen: boolean[] = new Array(numCourses).fill(false);
        const todo: number[] = [...next[start]];
        while (todo.length > 0) {
            const c = todo.pop()!;
            if (c === start) return false;   // came back: start is stuck in a loop
            if (seen[c]) continue;
            seen[c] = true;
            for (const d of next[c]) {
                todo.push(d);
            }
        }
    }
    return true;
}

Complexity

Time O(V · (V + E))Space O(V + E)

V is numCourses and E is prerequisites.length. Each of the V starts does a search over up to V courses and E arrows. Correct, but the same walks are repeated from many starts.

Optimized approach

Idea

Start from brute force

Brute force asks, for each course, whether it can reach itself. Each start walks the arrows from scratch, so the same courses are checked again and again.

Find the repeated work

The arrows from one course are walked again for every other start that reaches it. Kahn avoids this by taking each course exactly once, when it is free.

Define the state — what variables do I need?

waiting[c]: How many prerequisites of course c are not taken yet. 0 means course c is free.
ready: A queue of courses that are free and not taken yet.
taken: How many courses have been taken so far.

Define validity

A course is safe to take exactly when its waiting count is 0: every prerequisite is already taken, so nothing blocks it.

Define the transitions — when does each pointer move, and why is it safe?

Before the loop

Count waiting[a] for every pair [a, b]; push every course with waiting = 0 into ready

These courses have nothing to wait for, so they can be taken first.

Pop a course c from ready

taken++; for each course d that needs c, waiting[d]--; push d when waiting[d] becomes 0

Taking c satisfies one prerequisite for each course d that needs it. d becomes free only when all of its prerequisites are gone.

What does the current window add to the answer?

Each pop is one course taken for real. At the end, taken equals numCourses only if no course was left blocked.

Code & Implementation

optimal.cpp

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> next(numCourses);
        vector<int> waiting(numCourses, 0);   // prerequisites of each course not taken yet

        for (auto& p : prerequisites) {
            next[p[1]].push_back(p[0]);       // b unlocks a
            waiting[p[0]]++;                  // a waits for one more course
        }

        // Start with the courses that have nothing to wait for.
        queue<int> ready;
        for (int c = 0; c < numCourses; c++)
            if (waiting[c] == 0) ready.push(c);

        int taken = 0;
        while (!ready.empty()) {
            int c = ready.front();
            ready.pop();
            taken++;
            // Taking c satisfies one prerequisite of each course that needs it.
            for (int d : next[c]) {
                if (--waiting[d] == 0) ready.push(d);
            }
        }

        // Only a loop can leave courses untaken.
        return taken == numCourses;
    }
};

import java.util.*;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> next = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            next.add(new ArrayList<>());
        }
        int[] waiting = new int[numCourses];   // prerequisites of each course not taken yet

        for (int[] p : prerequisites) {
            next.get(p[1]).add(p[0]);          // b unlocks a
            waiting[p[0]]++;                   // a waits for one more course
        }

        // Start with the courses that have nothing to wait for.
        Queue<Integer> ready = new ArrayDeque<>();
        for (int c = 0; c < numCourses; c++) {
            if (waiting[c] == 0) ready.offer(c);
        }

        int taken = 0;
        while (!ready.isEmpty()) {
            int c = ready.poll();
            taken++;
            // Taking c satisfies one prerequisite of each course that needs it.
            for (int d : next.get(c)) {
                if (--waiting[d] == 0) ready.offer(d);
            }
        }

        // Only a loop can leave courses untaken.
        return taken == numCourses;
    }
}

from typing import List
from collections import deque

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        next_courses: List[List[int]] = [[] for _ in range(numCourses)]
        waiting = [0] * numCourses   # prerequisites of each course not taken yet

        for a, b in prerequisites:
            next_courses[b].append(a)   # b unlocks a
            waiting[a] += 1             # a waits for one more course

        # Start with the courses that have nothing to wait for.
        ready = deque([c for c in range(numCourses) if waiting[c] == 0])

        taken = 0
        while ready:
            c = ready.popleft()
            taken += 1
            # Taking c satisfies one prerequisite of each course that needs it.
            for d in next_courses[c]:
                waiting[d] -= 1
                if waiting[d] == 0:
                    ready.append(d)

        # Only a loop can leave courses untaken.
        return taken == numCourses

export function canFinish(numCourses: number, prerequisites: number[][]): boolean {
    const next: number[][] = Array.from({ length: numCourses }, () => []);
    const waiting: number[] = new Array(numCourses).fill(0);   // prerequisites of each course not taken yet

    for (const [a, b] of prerequisites) {
        next[b].push(a);       // b unlocks a
        waiting[a]++;          // a waits for one more course
    }

    // Start with the courses that have nothing to wait for.
    const ready: number[] = [];
    for (let c = 0; c < numCourses; c++) {
        if (waiting[c] === 0) ready.push(c);
    }

    let taken = 0;
    let head = 0;
    while (head < ready.length) {
        const c = ready[head++];
        taken++;
        // Taking c satisfies one prerequisite of each course that needs it.
        for (const d of next[c]) {
            waiting[d]--;
            if (waiting[d] === 0) ready.push(d);
        }
    }

    // Only a loop can leave courses untaken.
    return taken === numCourses;
}

Complexity

Time O(V + E)Space O(V + E)

Each course enters the queue once. Each arrow is read once, when its source course is taken. The adjacency list and the counts are the O(V + E) memory.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	From each course, follow the prerequisite arrows; if the walk returns to the start, it is stuck in a loop	O(V · (V + E))	O(V + E)
Optimal	Keep a count of unfinished prerequisites; take free courses from a queue; if every course gets taken, there is no loop	O(V + E)	O(V + E)

Why does this belong to this pattern?

Clues in the problem statement

“prerequisites [a, b]”Each pair is an arrow: course b must come before course a. The courses form a directed graph.
“can you finish all courses?”A yes or no question. It asks whether a loop exists, not for the order itself.
“courses that block each other”That is a loop. A loop means the processing order can never start.

directed graph of prerequisites+is there a loop?+Kahn: taken count equals V→Topological Sort — Kahn's algorithm, cycle check (taken == numCourses)

This is the anchor question of the cycle-detection sub-pattern. The sort is a tool here. If every course can be taken, a topological order exists, so there is no loop. If the queue runs dry early, the courses left over form a loop. Only the number of taken courses matters. The next two questions need different output: the cycle itself (GFG) and the safe nodes (LC 802).

Don't make this mistake

Using one visited set reports a loop that is not there

✗ bool dfs(int c) { if (visited[c]) return true; // seen before = loop? visited[c] = true; for (int d : next[c]) if (dfs(d)) return true; return false; }

✓ bool dfs(int c) { if (state[c] == ON_PATH) return true; // back on our own path: a real loop if (state[c] == DONE) return false; // finished earlier: safe to skip state[c] = ON_PATH; for (int d : next[c]) if (dfs(d)) return true; state[c] = DONE; return false; }

This is the undirected trick: remember everything seen and treat a revisit as a loop. On the dry-run courses (0 → 1, 0 → 2, 1 → 3, 2 → 3, 3 → 4), the walk goes 0 → 1 → 3 → 4 and finishes 3. Back at 0, it tries 0 → 2 → 3. Course 3 is already visited, so the wrong code says loop. But course 3 is finished, not on the current path. The real answer is true, and this code says false.

Counting the wrong course as waiting

✗ for (auto& p : prerequisites) { next[p[1]].push_back(p[0]); waiting[p[1]]++; // counts the course that is needed, not the one waiting }

✓ for (auto& p : prerequisites) { next[p[1]].push_back(p[0]); // b unlocks a waiting[p[0]]++; // a waits for one more course }

The count belongs to the course that has to wait, which is a (the first number). On the dry run the wrong count gives waiting = [2, 1, 1, 1, 0] instead of [0, 1, 1, 2, 1]. Only course 4 looks free, so the queue takes 4, nothing unlocks, and the code says false. The real answer is true.

Checking the empty queue instead of the count

✗ while (!ready.empty()) { /* take courses */ } return ready.empty(); // always true after the loop

✓ while (!ready.empty()) { /* take courses */ } return taken == numCourses;

When the loop ends, the queue is always empty, so this test always passes, even when courses are stuck. On example 2, [[1, 0], [0, 1]], no course is free at the start, the queue is empty at once, and the code says true. Count the courses you took instead.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Topological Sort translate into production architectures and low-level memory mechanics.

LLD Practice

Task Scheduler & Workflow Orchestrator

Resolving DAG build pipelines and asynchronous task dependency resolution.

Explore Track

C++ Internals

Static vs Global Linkage & Init Order Fiasco

Why compilers resolve static global variables as a DAG to prevent runtime crashes.

Explore Track

Detect Cycle in a Directed Graph