Solutions

1. Depth First Search

O(n + m) time | O(n + m) space, for n courses and m pairs

Intuition

We can represent courses as a graph where each course is a node and all its prerequisites point to it. Then we can take each course and recursively traverse through everything it points to. If we reach a course that is already on the current path, there is a circle.

Algorithm

Create a graph as an adjacency list, where each prerequisite points to all its dependencies.
Create a path hash set for the courses in the current traversal, and a finished hash set for finished courses.
Traverse through the graph from every course one by one.
- Return false when the traversal reaches a course that is already in path.
- If a course is already in finished, skip it.
- Add a course to path, and move it to finished once everything that depends on it has been traversed.
Return true.

start at course 0

1 / 6

Code

Recursive implementation

Code

def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    graph = buildGraph(numCourses, prerequisites)
    path = set()
    finished = set()
    for course in range(numCourses):
        if not dfs(graph, path, finished, course):
            return False
    return True


def dfs(graph: list[list[int]], path: set[int], finished: set[int], course: int) -> bool:
    if course in path:
        return False
    if course in finished:
        return True
    path.add(course)
    for dependency in graph[course]:
        if not dfs(graph, path, finished, dependency):
            return False
    path.remove(course)
    finished.add(course)
    return True


def buildGraph(numCourses: int, prerequisites: list[list[int]]) -> list[list[int]]:
    graph = [[] for _ in range(numCourses)]
    for course, prerequisite in prerequisites:
        graph[prerequisite].append(course)
    return graph

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @returns {boolean}
 */
var canFinish = function (numCourses, prerequisites) {
  const graph = buildGraph(numCourses, prerequisites)
  const path = new Set()
  const finished = new Set()
  for (let course = 0; course < numCourses; course++) {
    if (!dfs(graph, path, finished, course)) return false
  }
  return true
}

function dfs(graph, path, finished, course) {
  if (path.has(course)) return false
  if (finished.has(course)) return true
  path.add(course)
  for (const dependency of graph[course]) {
    if (!dfs(graph, path, finished, dependency)) return false
  }
  path.delete(course)
  finished.add(course)
  return true
}

function buildGraph(numCourses, prerequisites) {
  const graph = Array.from({ length: numCourses }, () => [])
  for (const [course, prerequisite] of prerequisites) graph[prerequisite].push(course)
  return graph
}

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = buildGraph(numCourses, prerequisites);
        Set<Integer> path = new HashSet<>();
        Set<Integer> finished = new HashSet<>();
        for (int course = 0; course < numCourses; course++) {
            if (!dfs(graph, path, finished, course)) return false;
        }
        return true;
    }

    private boolean dfs(List<List<Integer>> graph, Set<Integer> path, Set<Integer> finished, int course) {
        if (path.contains(course)) return false;
        if (finished.contains(course)) return true;
        path.add(course);
        for (int dependency : graph.get(course)) {
            if (!dfs(graph, path, finished, dependency)) return false;
        }
        path.remove(course);
        finished.add(course);
        return true;
    }

    private List<List<Integer>> buildGraph(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int course = 0; course < numCourses; course++) graph.add(new ArrayList<>());
        for (int[] pair : prerequisites) {
            int course = pair[0];
            int prerequisite = pair[1];
            graph.get(prerequisite).add(course);
        }
        return graph;
    }
}

Iterative implementation

Code

def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    graph = buildGraph(numCourses, prerequisites)
    path = set()
    finished = set()
    for start in range(numCourses):
        if start in finished:
            continue
        path.add(start)
        stack = [(start, 0)]
        while stack:
            course, at = stack.pop()
            if at == len(graph[course]):
                path.discard(course)
                finished.add(course)
                continue
            stack.append((course, at + 1))
            dependency = graph[course][at]
            if dependency in path:
                return False
            if dependency not in finished:
                path.add(dependency)
                stack.append((dependency, 0))
    return True


def buildGraph(numCourses: int, prerequisites: list[list[int]]) -> list[list[int]]:
    graph = [[] for _ in range(numCourses)]
    for course, prerequisite in prerequisites:
        graph[prerequisite].append(course)
    return graph

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @returns {boolean}
 */
var canFinish = function (numCourses, prerequisites) {
  const graph = buildGraph(numCourses, prerequisites)
  const path = new Set()
  const finished = new Set()
  for (let start = 0; start < numCourses; start++) {
    if (finished.has(start)) continue
    path.add(start)
    const stack = [[start, 0]]
    while (stack.length > 0) {
      const [course, at] = stack.pop()
      if (at === graph[course].length) {
        path.delete(course)
        finished.add(course)
        continue
      }
      stack.push([course, at + 1])
      const dependency = graph[course][at]
      if (path.has(dependency)) return false
      if (!finished.has(dependency)) {
        path.add(dependency)
        stack.push([dependency, 0])
      }
    }
  }
  return true
}

function buildGraph(numCourses, prerequisites) {
  const graph = Array.from({ length: numCourses }, () => [])
  for (const [course, prerequisite] of prerequisites) graph[prerequisite].push(course)
  return graph
}

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = buildGraph(numCourses, prerequisites);
        Set<Integer> path = new HashSet<>();
        Set<Integer> finished = new HashSet<>();
        for (int start = 0; start < numCourses; start++) {
            if (finished.contains(start)) continue;
            path.add(start);
            Deque<int[]> stack = new ArrayDeque<>();
            stack.push(new int[] { start, 0 });
            while (!stack.isEmpty()) {
                int[] top = stack.pop();
                int course = top[0];
                int at = top[1];
                if (at == graph.get(course).size()) {
                    path.remove(course);
                    finished.add(course);
                    continue;
                }
                stack.push(new int[] { course, at + 1 });
                int dependency = graph.get(course).get(at);
                if (path.contains(dependency)) return false;
                if (!finished.contains(dependency)) {
                    path.add(dependency);
                    stack.push(new int[] { dependency, 0 });
                }
            }
        }
        return true;
    }

    private List<List<Integer>> buildGraph(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int course = 0; course < numCourses; course++) graph.add(new ArrayList<>());
        for (int[] pair : prerequisites) {
            int course = pair[0];
            int prerequisite = pair[1];
            graph.get(prerequisite).add(course);
        }
        return graph;
    }
}

2. Topological Sort

O(n + m) time | O(n + m) space, for n courses and m pairs

Intuition

We can start from the courses that have no prerequisites. Mark them as finished and repeatedly move on to the courses that have no unfinished prerequisites left. If there are any unfinished courses at the end, there is a circle.

Algorithm

Create a graph as an adjacency list, where each prerequisite points to all its dependencies, and count how many prerequisites each course has.
Push every course that starts with no prerequisites onto a queue.
Pop each course from the queue one by one.
- Count it as finished.
- Decrease the prerequisite count of each of its dependencies, pushing the ones that reach zero.
Return whether every course was finished.

visit 0: push 1 and decrease prerequisite count

1 / 5

Code

from collections import deque


def canFinish(numCourses: int, prerequisites: list[list[int]]) -> bool:
    graph = [[] for _ in range(numCourses)]
    prerequisitesCount = [0] * numCourses
    for course, prerequisite in prerequisites:
        graph[prerequisite].append(course)
        prerequisitesCount[course] += 1

    queue = deque()
    for course in range(numCourses):
        if not prerequisitesCount[course]:
            queue.append(course)

    finished = 0
    while queue:
        course = queue.popleft()
        finished += 1
        for dependency in graph[course]:
            prerequisitesCount[dependency] -= 1
            if not prerequisitesCount[dependency]:
                queue.append(dependency)
    return finished == numCourses

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @returns {boolean}
 */
var canFinish = function (numCourses, prerequisites) {
  const graph = Array.from({ length: numCourses }, () => [])
  const prerequisitesCount = new Array(numCourses).fill(0)
  for (const [course, prerequisite] of prerequisites) {
    graph[prerequisite].push(course)
    prerequisitesCount[course]++
  }

  const queue = []
  for (let course = 0; course < numCourses; course++) {
    if (!prerequisitesCount[course]) queue.push(course)
  }

  let finished = 0
  for (let at = 0; at < queue.length; at++) {
    finished++
    for (const dependency of graph[queue[at]]) {
      if (--prerequisitesCount[dependency] === 0) queue.push(dependency)
    }
  }
  return finished === numCourses
}

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int course = 0; course < numCourses; course++) graph.add(new ArrayList<>());
        int[] prerequisitesCount = new int[numCourses];
        for (int[] pair : prerequisites) {
            int course = pair[0];
            int prerequisite = pair[1];
            graph.get(prerequisite).add(course);
            prerequisitesCount[course]++;
        }

        Deque<Integer> queue = new ArrayDeque<>();
        for (int course = 0; course < numCourses; course++) {
            if (prerequisitesCount[course] == 0) queue.add(course);
        }

        int finished = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            finished++;
            for (int dependency : graph.get(course)) {
                if (--prerequisitesCount[dependency] == 0) queue.add(dependency);
            }
        }
        return finished == numCourses;
    }
}