Coding problem · Medium · Graphs

Course Schedule

Medium Algorithms & data structures Seen at Amazon, Google, Meta, Uber

There are numCourses courses labelled 0..numCourses-1. prerequisites[i] = [a, b] means you must take b before a. Return true if you can finish all courses.

Example 1

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

Example 2

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: The two courses depend on each other.

Hints

Hint 1

This is cycle detection in a directed graph.

Hint 2

Kahn's algorithm: repeatedly take courses with no remaining prerequisites (in-degree 0).

Write and run your solution

Loading the editor… (JavaScript is required to run code in your browser.)

Solution and explanation

Show the solution

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

Kahn's topological sort: count in-degrees, start a queue with all courses that have none, and repeatedly 'take' a course, decrementing its dependants' in-degrees. If every course gets taken there is no cycle.

Reference solution

function canFinish(numCourses, prerequisites) {
  const indeg = new Array(numCourses).fill(0);
  const next = Array.from({ length: numCourses }, () => []);
  for (const [a, b] of prerequisites) { next[b].push(a); indeg[a]++; }
  const queue = [];
  indeg.forEach((d, i) => d === 0 && queue.push(i));
  let taken = 0;
  while (queue.length) {
    const c = queue.shift();
    taken++;
    for (const d of next[c]) if (--indeg[d] === 0) queue.push(d);
  }
  return taken === numCourses;
}

function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  const indeg = new Array<number>(numCourses).fill(0);
  const next: number[][] = Array.from({ length: numCourses }, () => []);
  for (const [a, b] of prerequisites) { next[b].push(a); indeg[a]++; }
  const queue = indeg.flatMap((d, i) => (d === 0 ? [i] : []));
  let taken = 0;
  while (queue.length) {
    const c = queue.shift()!;
    taken++;
    for (const d of next[c]) if (--indeg[d] === 0) queue.push(d);
  }
  return taken === numCourses;
}

from collections import deque

def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
    indeg = [0] * num_courses
    nxt: list[list[int]] = [[] for _ in range(num_courses)]
    for a, b in prerequisites:
        nxt[b].append(a)
        indeg[a] += 1
    queue = deque(i for i, d in enumerate(indeg) if d == 0)
    taken = 0
    while queue:
        c = queue.popleft()
        taken += 1
        for d in nxt[c]:
            indeg[d] -= 1
            if indeg[d] == 0:
                queue.append(d)
    return taken == num_courses

<?php

function canFinish(int $numCourses, array $prerequisites): bool
{
    $indeg = array_fill(0, $numCourses, 0);
    $next = array_fill(0, $numCourses, []);
    foreach ($prerequisites as [$a, $b]) {
        $next[$b][] = $a;
        $indeg[$a]++;
    }
    $queue = array_keys(array_filter($indeg, fn($d) => $d === 0));
    $taken = 0;
    while ($queue) {
        $c = array_shift($queue);
        $taken++;
        foreach ($next[$c] as $d) {
            if (--$indeg[$d] === 0) {
                $queue[] = $d;
            }
        }
    }
    return $taken === $numCourses;
}

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indeg = new int[numCourses];
        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]); indeg[p[0]]++; }
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) queue.add(i);
        int taken = 0;
        while (!queue.isEmpty()) {
            int c = queue.poll();
            taken++;
            for (int d : next.get(c)) if (--indeg[d] == 0) queue.add(d);
        }
        return taken == numCourses;
    }
}

Follow-up questions

Return a valid order (Course Schedule II).

Number of Islands · Medium
Find Deadlocked Transactions · Medium