MediumGraphs

Course Schedule

There are num_courses courses, numbered 0 to num_courses - 1. You get an array prerequisites of pairs [a, b], each meaning that course b has to be finished before course a can start. Return true if there is an order in which you can finish every course, and false if there is not.

Think of each pair as an arrow from b to a. The courses can all be finished exactly when those arrows never form a loop: a loop means each course on it waits for another one on it, so none of them can ever start. A pair [a, a], a course that needs itself, is the smallest loop. The same pair may appear more than once, which changes nothing. With no pairs at all, every course can be taken in any order, so the answer is true.

Examples

Input

num_courses = 5
prerequisites = [[2, 0], [2, 1], [3, 2], [4, 3]]

OutputtrueWhyTake 0 and 1 first, which unlocks 2, then 3, then 4. No arrow ever leads back.

Input

num_courses = 4
prerequisites = [[1, 0], [2, 1], [3, 2], [1, 3]]

OutputfalseWhyCourse 1 needs 3, 3 needs 2 and 2 needs 1: the loop 1 → 2 → 3 → 1 never lets any of them start. Course 0 alone is not enough.

Constraints

Courses: 1 ≤ num_courses ≤ 500
Pairs: 0 ≤ prerequisites.length ≤ 1,000
Values: 0 ≤ a, b < num_courses
Repeats: A pair can repeat, and a can equal b (a course that needs itself).
Time limit: 10 s per run, all cases

Run your code 2 more times to open the solutions. The idea sticks better after an attempt.

2 reference approaches in Python, from brute force to the one to reach for. Compare them with yours.

1 · DFS with three colours: look for an arrow back into the current path

O(n + p) time · O(n + p) space

Build an adjacency list from each prerequisite to the courses it unlocks, then walk it depth first with three states per course: 0 not seen, 1 on the current path, 2 finished. Meeting a course in state 1 means the walk came back into its own path, which is a loop. A finished course is never walked again, so each course and each pair is handled once. The deepest chain here is 500 courses, inside Python's default recursion limit of 1,000 frames.

def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
    unlocks: list[list[int]] = [[] for _ in range(num_courses)]
    for a, b in prerequisites:
        unlocks[b].append(a)
    state = [0] * num_courses  # 0 = not seen, 1 = on the current path, 2 = finished

    def has_loop(course: int) -> bool:
        state[course] = 1
        for nxt in unlocks[course]:
            if state[nxt] == 1:
                return True
            if state[nxt] == 0 and has_loop(nxt):
                return True
        state[course] = 2
        return False

    return not any(state[c] == 0 and has_loop(c) for c in range(num_courses))

2 · Kahn's topological sort: take courses whose prerequisites are done

O(n + p) time · O(n + p) space

recommended

Count how many prerequisites each course still waits for. Every course at zero can be taken now, so it goes into a deque. Taking a course lowers the count of each course it unlocks, and any count that drops to zero joins the queue. Courses on a loop never reach zero, so the answer is whether the number of courses taken equals num_courses. There is no recursion, so no depth limit either.

from collections import deque


def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
    unlocks: list[list[int]] = [[] for _ in range(num_courses)]
    waiting = [0] * num_courses  # prerequisites not yet taken
    for a, b in prerequisites:
        unlocks[b].append(a)
        waiting[a] += 1
    ready = deque(c for c in range(num_courses) if waiting[c] == 0)
    taken = 0
    while ready:
        course = ready.popleft()
        taken += 1
        for nxt in unlocks[course]:
            waiting[nxt] -= 1
            if waiting[nxt] == 0:
                ready.append(nxt)
    return taken == num_courses

2 reference approaches in JavaScript, from brute force to the one to reach for. Compare them with yours.

1 · DFS with three colours: look for an arrow back into the current path

O(n + p) time · O(n + p) space

Array.from with a callback builds one fresh array per course, the courses it unlocks. A Uint8Array holds each course's state: 0 not seen, 1 on the current path, 2 finished. The inner hasLoop returns true as soon as it reaches a course still marked 1, because the walk has come back into its own path. Finished courses are skipped, so every course and every pair is handled once.

function canFinish(numCourses, prerequisites) {
  const unlocks = Array.from({ length: numCourses }, () => []);
  for (const [a, b] of prerequisites) unlocks[b].push(a);
  const state = new Uint8Array(numCourses); // 0 = not seen, 1 = on the current path, 2 = finished

  function hasLoop(course) {
    state[course] = 1;
    for (const next of unlocks[course]) {
      if (state[next] === 1) return true;
      if (state[next] === 0 && hasLoop(next)) return true;
    }
    state[course] = 2;
    return false;
  }

  for (let c = 0; c < numCourses; c++) {
    if (state[c] === 0 && hasLoop(c)) return false;
  }
  return true;
}

2 · Kahn's topological sort: take courses whose prerequisites are done

O(n + p) time · O(n + p) space

recommended

waiting[c] counts the prerequisites course c has not had yet. Every course at zero goes into ready, an ordinary array read through a head index, so taking the next course costs O(1) where shift() would move the rest of the array. Each course taken lowers the counts of the courses it unlocks, and the ones that reach zero are pushed. Courses on a loop never get there, so the answer is whether head ends at numCourses.

function canFinish(numCourses, prerequisites) {
  const unlocks = Array.from({ length: numCourses }, () => []);
  const waiting = new Array(numCourses).fill(0); // prerequisites not yet taken
  for (const [a, b] of prerequisites) {
    unlocks[b].push(a);
    waiting[a]++;
  }
  const ready = [];
  for (let c = 0; c < numCourses; c++) if (waiting[c] === 0) ready.push(c);
  let head = 0;
  while (head < ready.length) {
    const course = ready[head++];
    for (const next of unlocks[course]) {
      if (--waiting[next] === 0) ready.push(next);
    }
  }
  return head === numCourses;
}

2 reference approaches in TypeScript, from brute force to the one to reach for. Compare them with yours.

1 · DFS with three colours: look for an arrow back into the current path

O(n + p) time · O(n + p) space

A number[][] adjacency list maps each course to the courses it unlocks, and a const enum State names the three colours: not seen, on the current path, finished. Reaching a course that is still OnPath means the walk came back into its own path, a loop. Finished courses are never walked again, so every course and pair is handled once.

const enum State { Unseen, OnPath, Done }

function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  const unlocks: number[][] = Array.from({ length: numCourses }, () => []);
  for (const [a, b] of prerequisites) unlocks[b].push(a);
  const state: State[] = new Array(numCourses).fill(State.Unseen);

  function hasLoop(course: number): boolean {
    state[course] = State.OnPath;
    for (const next of unlocks[course]) {
      if (state[next] === State.OnPath) return true;
      if (state[next] === State.Unseen && hasLoop(next)) return true;
    }
    state[course] = State.Done;
    return false;
  }

  for (let c = 0; c < numCourses; c++) {
    if (state[c] === State.Unseen && hasLoop(c)) return false;
  }
  return true;
}

2 · Kahn's topological sort: take courses whose prerequisites are done

O(n + p) time · O(n + p) space

recommended

waiting counts each course's prerequisites not yet taken. Courses at zero go into ready, read through a head index so each step is O(1). Taking a course lowers the counts of the courses it unlocks and queues the ones that reach zero. A course on a loop never reaches zero, so all courses are finishable exactly when head ends at numCourses.

function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  const unlocks: number[][] = Array.from({ length: numCourses }, () => []);
  const waiting: number[] = new Array(numCourses).fill(0);
  for (const [a, b] of prerequisites) {
    unlocks[b].push(a);
    waiting[a]++;
  }
  const ready: number[] = [];
  for (let c = 0; c < numCourses; c++) if (waiting[c] === 0) ready.push(c);
  let head = 0;
  while (head < ready.length) {
    const course = ready[head++];
    for (const next of unlocks[course]) {
      if (--waiting[next] === 0) ready.push(next);
    }
  }
  return head === numCourses;
}

2 reference approaches in Java, from brute force to the one to reach for. Compare them with yours.

1 · DFS with three colours: look for an arrow back into the current path

O(n + p) time · O(n + p) space

The adjacency list is a List<List<Integer>> from each course to the courses it unlocks, and a byte[] holds each course's state: 0 not seen, 1 on the current path, 2 finished. The helper hasLoop is a separate static method that receives both, and it returns true on meeting a course still in state 1. Finished courses are never walked again, so the work is linear.

import java.util.*;

public class Main {
    static boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> unlocks = new ArrayList<>(numCourses);
        for (int c = 0; c < numCourses; c++) unlocks.add(new ArrayList<>());
        for (int[] p : prerequisites) unlocks.get(p[1]).add(p[0]);
        byte[] state = new byte[numCourses]; // 0 = not seen, 1 = on the current path, 2 = finished
        for (int c = 0; c < numCourses; c++) {
            if (state[c] == 0 && hasLoop(c, unlocks, state)) return false;
        }
        return true;
    }

    static boolean hasLoop(int course, List<List<Integer>> unlocks, byte[] state) {
        state[course] = 1;
        for (int next : unlocks.get(course)) {
            if (state[next] == 1) return true;
            if (state[next] == 0 && hasLoop(next, unlocks, state)) return true;
        }
        state[course] = 2;
        return false;
    }
}

2 · Kahn's topological sort: take courses whose prerequisites are done

O(n + p) time · O(n + p) space

recommended

waiting[c] counts the prerequisites course c has not had yet. Courses at zero go into an ArrayDeque<Integer>; each one taken lowers the counts of the courses it unlocks, and every count that reaches zero is queued. Courses on a loop never reach zero, so the method returns whether the number taken equals numCourses.

import java.util.*;

public class Main {
    static boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> unlocks = new ArrayList<>(numCourses);
        for (int c = 0; c < numCourses; c++) unlocks.add(new ArrayList<>());
        int[] waiting = new int[numCourses]; // prerequisites not yet taken
        for (int[] p : prerequisites) {
            unlocks.get(p[1]).add(p[0]);
            waiting[p[0]]++;
        }
        ArrayDeque<Integer> ready = new ArrayDeque<>();
        for (int c = 0; c < numCourses; c++) if (waiting[c] == 0) ready.add(c);
        int taken = 0;
        while (!ready.isEmpty()) {
            int course = ready.poll();
            taken++;
            for (int next : unlocks.get(course)) {
                if (--waiting[next] == 0) ready.add(next);
            }
        }
        return taken == numCourses;
    }
}

2 reference approaches in Go, from brute force to the one to reach for. Compare them with yours.

1 · DFS with three colours: look for an arrow back into the current path

O(n + p) time · O(n + p) space

unlocks is a [][]int from each course to the courses it unlocks, and state a []uint8 with three values: not seen, on the current path, finished. A closure can only call itself if its variable exists first, so the code declares var hasLoop func(int) bool and assigns it on the next line. Reaching a course still on the path is a loop; finished courses are skipped, so the walk is linear.

package main

func canFinish(numCourses int, prerequisites [][]int) bool {
	unlocks := make([][]int, numCourses)
	for _, p := range prerequisites {
		unlocks[p[1]] = append(unlocks[p[1]], p[0])
	}
	const unseen, onPath, done = 0, 1, 2
	state := make([]uint8, numCourses)

	var hasLoop func(course int) bool
	hasLoop = func(course int) bool {
		state[course] = onPath
		for _, next := range unlocks[course] {
			if state[next] == onPath || state[next] == unseen && hasLoop(next) {
				return true
			}
		}
		state[course] = done
		return false
	}

	for c := 0; c < numCourses; c++ {
		if state[c] == unseen && hasLoop(c) {
			return false
		}
	}
	return true
}

2 · Kahn's topological sort: take courses whose prerequisites are done

O(n + p) time · O(n + p) space

recommended

waiting[c] counts the prerequisites of c not taken yet. The queue is a plain slice: courses at zero are appended, and ready[0] is taken off with ready = ready[1:], which only moves the slice header. Each course taken lowers the counts of the courses it unlocks. Courses on a loop never reach zero, so the answer is whether taken ends at numCourses.

package main

func canFinish(numCourses int, prerequisites [][]int) bool {
	unlocks := make([][]int, numCourses)
	waiting := make([]int, numCourses) // prerequisites not yet taken
	for _, p := range prerequisites {
		unlocks[p[1]] = append(unlocks[p[1]], p[0])
		waiting[p[0]]++
	}
	ready := make([]int, 0, numCourses)
	for c, w := range waiting {
		if w == 0 {
			ready = append(ready, c)
		}
	}
	taken := 0
	for len(ready) > 0 {
		course := ready[0]
		ready = ready[1:]
		taken++
		for _, next := range unlocks[course] {
			waiting[next]--
			if waiting[next] == 0 {
				ready = append(ready, next)
			}
		}
	}
	return taken == numCourses
}

2 reference approaches in C#, from brute force to the one to reach for. Compare them with yours.

1 · DFS with three colours: look for an arrow back into the current path

O(n + p) time · O(n + p) space

A List<int>[] maps each course to the courses it unlocks, and a byte[] holds the three states: 0 not seen, 1 on the current path, 2 finished. The local function HasLoop sees both without passing them, and returns true on reaching a course still in state 1. Finished courses are never walked again, so the work is linear.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static bool CanFinish(int numCourses, int[][] prerequisites)
    {
        var unlocks = new List<int>[numCourses];
        for (int c = 0; c < numCourses; c++) unlocks[c] = new List<int>();
        foreach (var p in prerequisites) unlocks[p[1]].Add(p[0]);
        var state = new byte[numCourses]; // 0 = not seen, 1 = on the current path, 2 = finished

        bool HasLoop(int course)
        {
            state[course] = 1;
            foreach (int next in unlocks[course])
            {
                if (state[next] == 1) return true;
                if (state[next] == 0 && HasLoop(next)) return true;
            }
            state[course] = 2;
            return false;
        }

        for (int c = 0; c < numCourses; c++)
        {
            if (state[c] == 0 && HasLoop(c)) return false;
        }
        return true;
    }
}

2 · Kahn's topological sort: take courses whose prerequisites are done

O(n + p) time · O(n + p) space

recommended

waiting[c] counts how many prerequisites of c are still untaken. Courses at zero go into a Queue<int>; each one dequeued lowers the counts of the courses it unlocks, and those that reach zero are enqueued. Courses on a loop never reach zero, so the method returns whether taken equals numCourses.

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution
{
    public static bool CanFinish(int numCourses, int[][] prerequisites)
    {
        var unlocks = new List<int>[numCourses];
        for (int c = 0; c < numCourses; c++) unlocks[c] = new List<int>();
        var waiting = new int[numCourses]; // prerequisites not yet taken
        foreach (var p in prerequisites)
        {
            unlocks[p[1]].Add(p[0]);
            waiting[p[0]]++;
        }
        var ready = new Queue<int>();
        for (int c = 0; c < numCourses; c++) if (waiting[c] == 0) ready.Enqueue(c);
        int taken = 0;
        while (ready.Count > 0)
        {
            int course = ready.Dequeue();
            taken++;
            foreach (int next in unlocks[course])
            {
                if (--waiting[next] == 0) ready.Enqueue(next);
            }
        }
        return taken == numCourses;
    }
}

2 reference approaches in C++, from brute force to the one to reach for. Compare them with yours.

1 · DFS with three colours: look for an arrow back into the current path

O(n + p) time · O(n + p) space

unlocks maps each course to the courses it unlocks, and state holds the three colours: 0 not seen, 1 on the current path, 2 finished. The helper hasLoop is a private member that takes both by reference, so nothing is copied per call. Reaching a course still in state 1 is a loop; finished courses are skipped, so the walk is linear.

#include <algorithm>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> unlocks(numCourses);
        for (const auto& p : prerequisites) unlocks[p[1]].push_back(p[0]);
        vector<char> state(numCourses, 0); // 0 = not seen, 1 = on the current path, 2 = finished
        for (int c = 0; c < numCourses; c++) {
            if (state[c] == 0 && hasLoop(c, unlocks, state)) return false;
        }
        return true;
    }

private:
    bool hasLoop(int course, const vector<vector<int>>& unlocks, vector<char>& state) {
        state[course] = 1;
        for (int next : unlocks[course]) {
            if (state[next] == 1) return true;
            if (state[next] == 0 && hasLoop(next, unlocks, state)) return true;
        }
        state[course] = 2;
        return false;
    }
};

2 · Kahn's topological sort: take courses whose prerequisites are done

O(n + p) time · O(n + p) space

recommended

waiting[c] counts the prerequisites of c not taken yet. Courses at zero go into a std::queue<int>; each one popped lowers the counts of the courses it unlocks, and those that reach zero are pushed. Courses on a loop never reach zero, so the method returns whether taken equals numCourses.

#include <algorithm>
#include <queue>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> unlocks(numCourses);
        vector<int> waiting(numCourses, 0); // prerequisites not yet taken
        for (const auto& p : prerequisites) {
            unlocks[p[1]].push_back(p[0]);
            waiting[p[0]]++;
        }
        queue<int> ready;
        for (int c = 0; c < numCourses; c++) if (waiting[c] == 0) ready.push(c);
        int taken = 0;
        while (!ready.empty()) {
            int course = ready.front();
            ready.pop();
            taken++;
            for (int next : unlocks[course]) {
                if (--waiting[next] == 0) ready.push(next);
            }
        }
        return taken == numCourses;
    }
};

2 reference approaches in C, from brute force to the one to reach for. Compare them with yours.

1 · DFS with three colours: look for an arrow back into the current path

O(n + p) time · O(n + p) space

C has no growable list, so the adjacency lists are built in two passes over the pairs: first count how many courses each course unlocks, turn the counts into start offsets, then write every course into its slot of one flat array. A char per course holds its state, 0 not seen, 1 on the current path, 2 finished, and the static helper has_loop returns true on reaching a course still in state 1. Free the three buffers before returning.

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

// The courses that course c unlocks are next[start[c]] .. next[start[c + 1] - 1].
static bool has_loop(int course, const int* start, const int* next, char* state) {
    state[course] = 1; // on the current path
    for (int k = start[course]; k < start[course + 1]; k++) {
        int after = next[k];
        if (state[after] == 1) return true;
        if (state[after] == 0 && has_loop(after, start, next, state)) return true;
    }
    state[course] = 2; // finished
    return false;
}

bool canFinish(int numCourses, int** prerequisites, int prerequisitesSize, int* prerequisitesColSize) {
    int* start = calloc(numCourses + 1, sizeof *start);
    int* next = malloc((prerequisitesSize + 1) * sizeof *next);
    char* state = calloc(numCourses, 1);

    for (int i = 0; i < prerequisitesSize; i++) start[prerequisites[i][1] + 1]++; // count
    for (int c = 0; c < numCourses; c++) start[c + 1] += start[c];                // offsets
    int* fill = malloc((numCourses + 1) * sizeof *fill);
    memcpy(fill, start, (numCourses + 1) * sizeof *fill);
    for (int i = 0; i < prerequisitesSize; i++) next[fill[prerequisites[i][1]]++] = prerequisites[i][0];
    free(fill);

    bool ok = true;
    for (int c = 0; c < numCourses && ok; c++) {
        if (state[c] == 0 && has_loop(c, start, next, state)) ok = false;
    }
    free(start);
    free(next);
    free(state);
    return ok;
}

2 · Kahn's topological sort: take courses whose prerequisites are done

O(n + p) time · O(n + p) space

recommended

The same flat adjacency lists, plus waiting[c], the number of prerequisites course c has not had yet. The queue is a plain int array of numCourses slots with a read and a write index: every course enters it at most once, when its count reaches zero, so it never overflows. The answer is whether all numCourses courses were taken.

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

bool canFinish(int numCourses, int** prerequisites, int prerequisitesSize, int* prerequisitesColSize) {
    int* start = calloc(numCourses + 1, sizeof *start);
    int* next = malloc((prerequisitesSize + 1) * sizeof *next);
    int* waiting = calloc(numCourses, sizeof *waiting); // prerequisites not yet taken
    int* queue = malloc(numCourses * sizeof *queue);

    for (int i = 0; i < prerequisitesSize; i++) {
        start[prerequisites[i][1] + 1]++;
        waiting[prerequisites[i][0]]++;
    }
    for (int c = 0; c < numCourses; c++) start[c + 1] += start[c];
    int* fill = malloc((numCourses + 1) * sizeof *fill);
    memcpy(fill, start, (numCourses + 1) * sizeof *fill);
    for (int i = 0; i < prerequisitesSize; i++) next[fill[prerequisites[i][1]]++] = prerequisites[i][0];
    free(fill);

    int head = 0, tail = 0;
    for (int c = 0; c < numCourses; c++) {
        if (waiting[c] == 0) queue[tail++] = c;
    }
    while (head < tail) {
        int course = queue[head++];
        for (int k = start[course]; k < start[course + 1]; k++) {
            if (--waiting[next[k]] == 0) queue[tail++] = next[k];
        }
    }
    int taken = tail; // every course that ever entered the queue was taken

    free(start);
    free(next);
    free(waiting);
    free(queue);
    return taken == numCourses;
}

2 reference approaches in Kotlin, from brute force to the one to reach for. Compare them with yours.

1 · DFS with three colours: look for an arrow back into the current path

O(n + p) time · O(n + p) space

List(numCourses) { mutableListOf<Int>() } maps each course to the courses it unlocks, and an IntArray holds each course's state: 0 not seen, 1 on the current path, 2 finished. The local function hasLoop sees both without passing them, and returns true on meeting a course still in state 1. Finished courses are never walked again, so the work is linear.

class Solution {
    fun canFinish(numCourses: Int, prerequisites: Array<IntArray>): Boolean {
        val unlocks = List(numCourses) { mutableListOf<Int>() }
        for ((course, before) in prerequisites) unlocks[before].add(course)
        val state = IntArray(numCourses) // 0 = not seen, 1 = on the current path, 2 = finished

        fun hasLoop(course: Int): Boolean {
            state[course] = 1
            for (next in unlocks[course]) {
                if (state[next] == 1) return true
                if (state[next] == 0 && hasLoop(next)) return true
            }
            state[course] = 2
            return false
        }

        return (0 until numCourses).none { state[it] == 0 && hasLoop(it) }
    }
}

2 · Kahn's topological sort: take courses whose prerequisites are done

O(n + p) time · O(n + p) space

recommended

waiting[c] counts the prerequisites course c has not had yet. Courses at zero go into an ArrayDeque<Int>, Kotlin's own double-ended queue; each one taken lowers the counts of the courses it unlocks, and every count that reaches zero is queued. Courses on a loop never reach zero, so the method returns whether the number taken equals numCourses.

class Solution {
    fun canFinish(numCourses: Int, prerequisites: Array<IntArray>): Boolean {
        val unlocks = List(numCourses) { mutableListOf<Int>() }
        val waiting = IntArray(numCourses) // prerequisites not yet taken
        for ((course, before) in prerequisites) {
            unlocks[before].add(course)
            waiting[course]++
        }
        val ready = ArrayDeque<Int>()
        for (c in 0 until numCourses) if (waiting[c] == 0) ready.addLast(c)
        var taken = 0
        while (ready.isNotEmpty()) {
            val course = ready.removeFirst()
            taken++
            for (next in unlocks[course]) {
                if (--waiting[next] == 0) ready.addLast(next)
            }
        }
        return taken == numCourses
    }
}

2 reference approaches in Rust, from brute force to the one to reach for. Compare them with yours.

1 · DFS with three colours: look for an arrow back into the current path

O(n + p) time · O(n + p) space

The pairs arrive as i32, so they are cast to usize once while building unlocks: Vec<Vec<usize>>. A small enum State names the three colours, and the helper has_loop is an associated function that borrows the lists and takes &mut [State], so the borrow checker is happy with the recursion. Reaching a course still OnPath means a loop; finished courses are never walked again.

#[derive(Clone, Copy, PartialEq)]
enum State {
    New,
    OnPath,
    Done,
}

impl Solution {
    pub fn can_finish(num_courses: i32, prerequisites: Vec<Vec<i32>>) -> bool {
        let n = num_courses as usize;
        let mut unlocks: Vec<Vec<usize>> = vec![Vec::new(); n];
        for pair in &prerequisites {
            unlocks[pair[1] as usize].push(pair[0] as usize);
        }
        let mut state = vec![State::New; n];
        !(0..n).any(|c| state[c] == State::New && Self::has_loop(c, &unlocks, &mut state))
    }

    fn has_loop(course: usize, unlocks: &[Vec<usize>], state: &mut [State]) -> bool {
        state[course] = State::OnPath;
        for &next in &unlocks[course] {
            let found = match state[next] {
                State::OnPath => true,                              // an arrow back into the path
                State::New => Self::has_loop(next, unlocks, state), // not walked yet
                State::Done => false,                               // already known loop-free
            };
            if found {
                return true;
            }
        }
        state[course] = State::Done;
        false
    }
}

2 · Kahn's topological sort: take courses whose prerequisites are done

O(n + p) time · O(n + p) space

recommended

waiting[c] counts the prerequisites course c has not had yet. Courses at zero go into a VecDeque<usize>; each one taken lowers the counts of the courses it unlocks, and every count that reaches zero is queued. while let Some(course) = ready.pop_front() runs until the queue is empty, and the answer is whether the number taken equals the number of courses.

use std::collections::VecDeque;

impl Solution {
    pub fn can_finish(num_courses: i32, prerequisites: Vec<Vec<i32>>) -> bool {
        let n = num_courses as usize;
        let mut unlocks: Vec<Vec<usize>> = vec![Vec::new(); n];
        let mut waiting = vec![0usize; n]; // prerequisites not yet taken
        for pair in &prerequisites {
            let (course, before) = (pair[0] as usize, pair[1] as usize);
            unlocks[before].push(course);
            waiting[course] += 1;
        }
        let mut ready: VecDeque<usize> = (0..n).filter(|&c| waiting[c] == 0).collect();
        let mut taken = 0;
        while let Some(course) = ready.pop_front() {
            taken += 1;
            for &next in &unlocks[course] {
                waiting[next] -= 1;
                if waiting[next] == 0 {
                    ready.push_back(next);
                }
            }
        }
        taken == n
    }
}

2 reference approaches in Swift, from brute force to the one to reach for. Compare them with yours.

1 · DFS with three colours: look for an arrow back into the current path

O(n + p) time · O(n + p) space

unlocks is an [[Int]] from each course to the courses it unlocks, and an enum Mark names the three states. The nested function hasLoop captures both, so the recursion is just hasLoop(next); it returns true on reaching a course still .onPath. Finished courses are never walked again, so the work is linear.

class Solution {
    enum Mark { case unseen, onPath, done }

    func canFinish(_ numCourses: Int, _ prerequisites: [[Int]]) -> Bool {
        var unlocks = [[Int]](repeating: [], count: numCourses)
        for pair in prerequisites {
            unlocks[pair[1]].append(pair[0])
        }
        var mark = [Mark](repeating: .unseen, count: numCourses)

        func hasLoop(_ course: Int) -> Bool {
            mark[course] = .onPath
            for next in unlocks[course] {
                if mark[next] == .onPath { return true }
                if mark[next] == .unseen && hasLoop(next) { return true }
            }
            mark[course] = .done
            return false
        }

        for course in 0..<numCourses where mark[course] == .unseen {
            if hasLoop(course) { return false }
        }
        return true
    }
}

2 · Kahn's topological sort: take courses whose prerequisites are done

O(n + p) time · O(n + p) space

recommended

waiting[c] counts the prerequisites course c has not had yet. The standard library has no queue type, so the queue is an [Int] read through an index head instead of removeFirst(), which would shift the whole array. Each course taken lowers the counts of the courses it unlocks, and every count that reaches zero is appended. The answer is whether every course entered the queue.

class Solution {
    func canFinish(_ numCourses: Int, _ prerequisites: [[Int]]) -> Bool {
        var unlocks = [[Int]](repeating: [], count: numCourses)
        var waiting = [Int](repeating: 0, count: numCourses) // prerequisites not yet taken
        for pair in prerequisites {
            unlocks[pair[1]].append(pair[0])
            waiting[pair[0]] += 1
        }
        var queue = (0..<numCourses).filter { waiting[$0] == 0 }
        var head = 0
        while head < queue.count {
            let course = queue[head]
            head += 1
            for next in unlocks[course] {
                waiting[next] -= 1
                if waiting[next] == 0 { queue.append(next) }
            }
        }
        return queue.count == numCourses // every course that entered the queue was taken
    }
}

2 reference approaches in PHP, from brute force to the one to reach for. Compare them with yours.

1 · DFS with three colours: look for an arrow back into the current path

O(n + p) time · O(n + p) space

array_fill(0, $numCourses, []) gives each course an empty list of the courses it unlocks, and $state holds each course's colour: 0 not seen, 1 on the current path, 2 finished. The private method hasLoop takes $state by reference, array &$state, so every recursive call writes the same array; without the & each call would get its own copy and the finished marks would be lost.

<?php

class Solution {
    /**
     * @param int $numCourses
     * @param int[][] $prerequisites
     * @return bool
     */
    function canFinish(int $numCourses, array $prerequisites): bool {
        $unlocks = array_fill(0, $numCourses, []);
        foreach ($prerequisites as [$course, $before]) {
            $unlocks[$before][] = $course;
        }
        $state = array_fill(0, $numCourses, 0); // 0 = not seen, 1 = on the current path, 2 = finished
        for ($c = 0; $c < $numCourses; $c++) {
            if ($state[$c] === 0 && $this->hasLoop($c, $unlocks, $state)) {
                return false;
            }
        }
        return true;
    }

    private function hasLoop(int $course, array $unlocks, array &$state): bool {
        $state[$course] = 1;
        foreach ($unlocks[$course] as $next) {
            if ($state[$next] === 1) {
                return true;
            }
            if ($state[$next] === 0 && $this->hasLoop($next, $unlocks, $state)) {
                return true;
            }
        }
        $state[$course] = 2;
        return false;
    }
}

2 · Kahn's topological sort: take courses whose prerequisites are done

O(n + p) time · O(n + p) space

recommended

$waiting[$c] counts the prerequisites course $c has not had yet. Courses at zero go into an SplQueue; each one taken lowers the counts of the courses it unlocks, and every count that reaches zero is enqueued. Courses on a loop never reach zero, so the method returns whether the number taken equals $numCourses.

<?php

class Solution {
    /**
     * @param int $numCourses
     * @param int[][] $prerequisites
     * @return bool
     */
    function canFinish(int $numCourses, array $prerequisites): bool {
        $unlocks = array_fill(0, $numCourses, []);
        $waiting = array_fill(0, $numCourses, 0); // prerequisites not yet taken
        foreach ($prerequisites as [$course, $before]) {
            $unlocks[$before][] = $course;
            $waiting[$course]++;
        }
        $ready = new SplQueue();
        foreach ($waiting as $c => $count) {
            if ($count === 0) {
                $ready->enqueue($c);
            }
        }
        $taken = 0;
        while (!$ready->isEmpty()) {
            $course = $ready->dequeue();
            $taken++;
            foreach ($unlocks[$course] as $next) {
                if (--$waiting[$next] === 0) {
                    $ready->enqueue($next);
                }
            }
        }
        return $taken === $numCourses;
    }
}

2 reference approaches in Ruby, from brute force to the one to reach for. Compare them with yours.

1 · DFS with three colours: look for an arrow back into the current path

O(n + p) time · O(n + p) space

Array.new(num_courses) { [] } gives each course its own list of the courses it unlocks, and state holds each course's colour as a symbol: :new, :on_path or :done. The helper loop? returns true on reaching a course still :on_path; the main method asks whether none? of the unvisited courses starts a loop.

# @param {Integer} num_courses
# @param {Integer[][]} prerequisites
# @return {Boolean}
def can_finish(num_courses, prerequisites)
  unlocks = Array.new(num_courses) { [] }
  prerequisites.each { |course, before| unlocks[before] << course }
  state = Array.new(num_courses, :new)
  (0...num_courses).none? { |c| state[c] == :new && loop?(c, unlocks, state) }
end

def loop?(course, unlocks, state)
  state[course] = :on_path
  unlocks[course].each do |nxt|
    return true if state[nxt] == :on_path
    return true if state[nxt] == :new && loop?(nxt, unlocks, state)
  end
  state[course] = :done
  false
end

2 · Kahn's topological sort: take courses whose prerequisites are done

O(n + p) time · O(n + p) space

recommended

waiting[c] counts the prerequisites course c has not had yet. The courses at zero start the queue, a plain Array used with push and shift; each one taken lowers the counts of the courses it unlocks, and every count that reaches zero is pushed. Courses on a loop never reach zero, so the method returns whether the number taken equals num_courses.

# @param {Integer} num_courses
# @param {Integer[][]} prerequisites
# @return {Boolean}
def can_finish(num_courses, prerequisites)
  unlocks = Array.new(num_courses) { [] }
  waiting = Array.new(num_courses, 0) # prerequisites not yet taken
  prerequisites.each do |course, before|
    unlocks[before] << course
    waiting[course] += 1
  end
  ready = (0...num_courses).select { |c| waiting[c].zero? }
  taken = 0
  until ready.empty?
    course = ready.shift
    taken += 1
    unlocks[course].each do |nxt|
      waiting[nxt] -= 1
      ready.push(nxt) if waiting[nxt].zero?
    end
  end
  taken == num_courses
end

2 reference approaches in Dart, from brute force to the one to reach for. Compare them with yours.

1 · DFS with three colours: look for an arrow back into the current path

O(n + p) time · O(n + p) space

List.generate(numCourses, (_) => <int>[]) gives each course its own list of the courses it unlocks, and an enum Mark names the three states. The local function hasLoop captures both, so the recursion is just hasLoop(next); it returns true on reaching a course still Mark.onPath. Finished courses are never walked again, so the work is linear.

enum Mark { unseen, onPath, done }

class Solution {
  bool canFinish(int numCourses, List<List<int>> prerequisites) {
    final unlocks = List.generate(numCourses, (_) => <int>[]);
    for (final [course, before] in prerequisites) {
      unlocks[before].add(course);
    }
    final mark = List.filled(numCourses, Mark.unseen);

    bool hasLoop(int course) {
      mark[course] = Mark.onPath;
      for (final next in unlocks[course]) {
        if (mark[next] == Mark.onPath) return true;
        if (mark[next] == Mark.unseen && hasLoop(next)) return true;
      }
      mark[course] = Mark.done;
      return false;
    }

    for (var c = 0; c < numCourses; c++) {
      if (mark[c] == Mark.unseen && hasLoop(c)) return false;
    }
    return true;
  }
}

2 · Kahn's topological sort: take courses whose prerequisites are done

O(n + p) time · O(n + p) space

recommended

waiting[c] counts the prerequisites course c has not had yet. Courses at zero go into a Queue<int> from dart:collection; each one taken lowers the counts of the courses it unlocks, and every count that reaches zero is added. Courses on a loop never reach zero, so the method returns whether the number taken equals numCourses.

import 'dart:collection';

class Solution {
  bool canFinish(int numCourses, List<List<int>> prerequisites) {
    final unlocks = List.generate(numCourses, (_) => <int>[]);
    final waiting = List.filled(numCourses, 0); // prerequisites not yet taken
    for (final [course, before] in prerequisites) {
      unlocks[before].add(course);
      waiting[course]++;
    }
    final ready = Queue<int>.of([
      for (var c = 0; c < numCourses; c++)
        if (waiting[c] == 0) c,
    ]);
    var taken = 0;
    while (ready.isNotEmpty) {
      final course = ready.removeFirst();
      taken++;
      for (final next in unlocks[course]) {
        if (--waiting[next] == 0) ready.add(next);
      }
    }
    return taken == numCourses;
  }
}

2 reference approaches in Scala, from brute force to the one to reach for. Compare them with yours.

1 · DFS with three colours: look for an arrow back into the current path

O(n + p) time · O(n + p) space

unlocks is an Array[List[Int]], each course's list built by prepending with ::, and an Array[Byte] holds the states: 0 not seen, 1 on the current path, 2 finished. The helper hasLoop walks its list with a while loop and a found flag instead of returning from inside a foreach, which Scala 3 no longer supports; it stops early once a loop is found.

object Solution {
  def canFinish(numCourses: Int, prerequisites: Array[Array[Int]]): Boolean = {
    val unlocks = Array.fill(numCourses)(List.empty[Int])
    for (Array(course, before) <- prerequisites) unlocks(before) = course :: unlocks(before)
    val state = new Array[Byte](numCourses) // 0 = not seen, 1 = on the current path, 2 = finished
    var c = 0
    var ok = true
    while (ok && c < numCourses) {
      if (state(c) == 0 && hasLoop(c, unlocks, state)) ok = false
      c += 1
    }
    ok
  }

  private def hasLoop(course: Int, unlocks: Array[List[Int]], state: Array[Byte]): Boolean = {
    state(course) = 1
    var rest = unlocks(course)
    var found = false
    while (!found && rest.nonEmpty) {
      val next = rest.head
      found = state(next) == 1 || (state(next) == 0 && hasLoop(next, unlocks, state))
      rest = rest.tail
    }
    if (!found) state(course) = 2
    found
  }
}

2 · Kahn's topological sort: take courses whose prerequisites are done

O(n + p) time · O(n + p) space

recommended

waiting(c) counts the prerequisites course c has not had yet. Courses at zero go into a mutable.Queue[Int]; each one taken lowers the counts of the courses it unlocks, and every count that reaches zero is enqueued. No early exit is needed, so a plain for over each list is fine. Courses on a loop never reach zero, so the method returns whether the number taken equals numCourses.

import scala.collection.mutable

object Solution {
  def canFinish(numCourses: Int, prerequisites: Array[Array[Int]]): Boolean = {
    val unlocks = Array.fill(numCourses)(List.empty[Int])
    val waiting = new Array[Int](numCourses) // prerequisites not yet taken
    for (Array(course, before) <- prerequisites) {
      unlocks(before) = course :: unlocks(before)
      waiting(course) += 1
    }
    val ready = mutable.Queue.from((0 until numCourses).filter(waiting(_) == 0))
    var taken = 0
    while (ready.nonEmpty) {
      val course = ready.dequeue()
      taken += 1
      for (next <- unlocks(course)) {
        waiting(next) -= 1
        if (waiting(next) == 0) ready.enqueue(next)
      }
    }
    taken == numCourses
  }
}

FAQ for Dart

Why List.generate and not List.filled(numCourses, <int>[])?

List.filled puts the same object in every slot, so with a list as the fill value every course would share one adjacency list. List.generate calls its function once per index and gives each course a new <int>[]. List.filled(numCourses, 0) is fine for waiting because ints are values.

What does for (final [course, before] in prerequisites) do?

It is a list pattern, available since Dart 3: each pair is matched against [course, before], binding its two elements. Each pair [a, b] means b comes before a. A pair of any other length would throw a StateError, which here cannot happen.

Why Queue instead of removeAt(0) on a List?

List.removeAt(0) shifts every remaining element down, O(n) per call. Queue from dart:collection is a ListQueue by default, a ring buffer with O(1) add and removeFirst.

Why does a visited bool list give wrong answers?

One flag cannot tell "on the current path" from "finished". In [[1, 0], [2, 0], [3, 1], [3, 2]] course 3 is reached from 1 and again from 2, which is not a loop. Three states fix it; dropping the finished state instead makes the DFS re-walk shared courses, and on the large hidden case it never ends.

How do I return a valid order instead of a bool?

In the Kahn version, keep final order = <int>[] and call order.add(course) where the loop counts. Return order.length == numCourses ? order : [] from a method declared List<int>.

Keep going

Binary Tree Level Order Traversal36 / 40 · Trees · Medium

Try Course Schedule in Python (Course Schedule in Python), JavaScript (Course Schedule in JavaScript), TypeScript (Course Schedule in TypeScript), Java (Course Schedule in Java), Go (Course Schedule in Go), C# (Course Schedule in C#), C++ (Course Schedule in C++), C (Course Schedule in C), Kotlin (Course Schedule in Kotlin), Rust (Course Schedule in Rust), Swift (Course Schedule in Swift), PHP (Course Schedule in PHP), Ruby (Course Schedule in Ruby) or Scala (Course Schedule in Scala) instead.

can_finish.dart

Dart 3.7

Not run yet

+ 8 hidden

Input

num_courses = 5
prerequisites = [[2, 0], [2, 1], [3, 2], [4, 3]]

Expected

true

Take 0 and 1 first, which unlocks 2, then 3, then 4. No arrow ever leads back.