Course Completion Feasibility: detect cycles in prerequisite graphs

You're midway through an Amazon onsite when the interviewer says: "You have a list of courses and some of them have prerequisites. Can you determine if it's even possible to finish all the courses?" This is Course Completion Feasibility, also known as Course Schedule on LeetCode and the Blind 75. It's one of the most frequently asked graph problems at Amazon, Google, Meta, and Adobe. The core question is whether a directed graph contains a cycle, and solving it requires understanding DFS with three-state node coloring.

TL;DR

Model courses and prerequisites as a directed graph. Build an adjacency list and run DFS on every unvisited node. Use a three-state visit array (unvisited, visiting, visited) to detect cycles. If DFS ever encounters a node that is currently in the "visiting" state, a cycle exists and you return false. If all nodes complete without hitting a cycle, return true. Time and space are both O(V + E).

Why This Problem Matters

Course Completion Feasibility is the gateway to topological sorting, a concept that appears in build systems, package managers, task schedulers, and compiler dependency resolution. Understanding cycle detection in directed graphs unlocks a whole family of problems: course ordering, parallel task scheduling, dependency validation, and deadlock detection. Interviewers use this problem because it tests whether you can translate a real-world dependency scenario into a graph algorithm.

Understanding the Problem

Given numCourses (labeled 0 to numCourses-1) and an array of prerequisite pairs where [a, b] means "course b must be completed before course a," determine if all courses can be finished.

canFinish(2, [[1,0]]) => true
canFinish(2, [[1,0],[0,1]]) => false

The first example has a simple dependency chain: take course 0 first, then course 1.

The second example has a circular dependency: course 0 requires course 1, and course 1 requires course 0. Neither can be taken first.

The problem reduces to: does the directed prerequisite graph contain a cycle? If yes, completion is impossible. If no, a valid ordering exists.

The Key Insight: Three-State Coloring

A naive approach might use a simple visited boolean, but that fails for directed graphs. Consider a diamond-shaped graph where two paths converge on the same node. A simple boolean would incorrectly report a cycle when revisiting a fully explored node via a different path.

The solution uses three states per node:

• Unvisited (0): Node has not been explored yet.
• Visiting (1): Node is on the current DFS path (recursion is still active for this node).
• Visited (2): Node and all its descendants have been fully explored.

The critical rule: if DFS reaches a node in the "visiting" state, that node is an ancestor on the current path, which means a back edge (and therefore a cycle) exists. If a node is "visited," it was fully explored in a previous DFS call and is safe to skip.

Solution Approach

1. Build an adjacency list from the prerequisites array. For each pair [a, b], add an edge from b to a (b must come before a).
2. Initialize a visit status array of size numCourses, all set to 0 (unvisited).
3. Run DFS from each unvisited node. If any DFS call detects a cycle, return false.
4. In the DFS helper: mark the node as visiting (1), recurse on all neighbors, then mark as visited (2). If a neighbor is visiting (1), return true (cycle found). If visited (2), skip it.

Walking Through a Larger Example

Consider canFinish(4, [[1,0],[2,0],[3,1],[3,2]]), which forms a diamond-shaped DAG:

Course 0 is the root with no prerequisites. Courses 1 and 2 depend on course 0. Course 3 depends on both 1 and 2. There is no cycle, so the answer is true.

Here is the DFS state evolution starting from course 0:

DFS starts at course 0, marks it as visiting, then explores course 1 (visiting), then course 3 (visiting). Course 3 has no unvisited neighbors, so it becomes visited. Control returns to course 1, which also becomes visited. Then DFS explores course 2, which leads to course 3 (already visited, skip). Course 2 becomes visited. Finally course 0 becomes visited. No cycle detected.

Cycle Detection Walk

For canFinish(3, [[0,1],[1,2],[2,0]]), where 0 depends on 1, 1 depends on 2, and 2 depends on 0:

DFS starts at 0 (visiting), goes to 1 (visiting), then 2 (visiting). Course 2 has neighbor 0, which is already in state 1 (visiting). This is a back edge, confirming a cycle. Return false immediately.

Edge Cases

No Prerequisites

When the prerequisites array is empty, every course is independent. The adjacency list has no edges, and DFS trivially marks each course as visited with no cycle.

Self-Loops

A prerequisite like [0, 0] (course 0 requires itself) creates a self-loop. DFS marks course 0 as visiting, then tries to visit course 0 again and finds it in the visiting state. Cycle detected.

Disconnected Components

Not all courses need to be connected. If courses form multiple disconnected subgraphs, the outer loop in the main function handles this by running DFS from every unvisited node. A cycle in any component means false.

Implementation

Prefer a different language? Jump to solutions in other languages.

import java.util.*;

public class Solution {

  public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> adjList = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) {
      adjList.add(new ArrayList<>());
    }

    for (int[] prerequisite : prerequisites) {
      adjList.get(prerequisite[1]).add(prerequisite[0]);
    }

    int[] visitStatus = new int[numCourses];

    for (int i = 0; i < numCourses; i++) {
      if (hasCycle(i, adjList, visitStatus)) {
        return false;
      }
    }

    return true;
  }

  private boolean hasCycle(int course, List<List<Integer>> adjList, int[] visitStatus) {
    if (visitStatus[course] == 1) {
      return true;
    }
    if (visitStatus[course] == 2) {
      return false;
    }

    visitStatus[course] = 1;

    for (int nextCourse : adjList.get(course)) {
      if (hasCycle(nextCourse, adjList, visitStatus)) {
        return true;
      }
    }

    visitStatus[course] = 2;
    return false;
  }
}

The hasCycle method is the recursive DFS engine. The visit status array with three states is the key: state 1 (visiting) means the node is on the current recursion stack, and encountering it again proves a cycle exists. State 2 (visited) means the node was fully explored in a prior call and can safely be skipped.

Complexity Analysis

Time: O(V + E)

Building the adjacency list scans all E prerequisite pairs once. The DFS visits each of the V courses at most once (the three-state guard prevents re-exploration). Each edge is traversed once during DFS. Total work: O(V + E).

Space: O(V + E)

The adjacency list stores all E edges. The visit status array uses V space. The recursion stack can be at most V deep (a linear chain of prerequisites). Total: O(V + E).

BFS Alternative: Kahn's Algorithm

Instead of DFS cycle detection, you can use BFS-based topological sort (Kahn's algorithm):

1. Compute in-degrees for all nodes.
2. Enqueue all nodes with in-degree 0.
3. Process the queue: for each dequeued node, decrement the in-degree of its neighbors. If a neighbor's in-degree reaches 0, enqueue it.
4. If the total number of processed nodes equals numCourses, no cycle exists.

The C++ and Go solutions below use this BFS approach. Same O(V + E) time and space. BFS avoids deep recursion, making it preferable when the prerequisite chain could be thousands of courses long.

Common Mistakes

• Using a boolean visited array instead of three states. A simple true/false flag cannot distinguish between a node on the current DFS path (cycle indicator) and a node fully explored in a previous DFS call (safe to skip). This causes false positives on diamond-shaped DAGs.

• Building the adjacency list backwards. The pair [a, b] means "b must come before a," so the edge goes from b to a. Reversing this direction changes the semantics and leads to incorrect cycle detection for asymmetric graphs.

• Forgetting to mark nodes as visited after DFS completes. If you mark a node as visiting but never update it to visited after exploring all neighbors, subsequent DFS calls will incorrectly report cycles.

• Not handling disconnected components. If you only run DFS from node 0, you miss cycles in components not reachable from node 0. The outer loop must iterate through all nodes.

Interview Tips

• Draw the graph. Sketch a small example with 3-4 nodes and walk through the DFS, showing the three states at each step. This demonstrates that you understand the algorithm visually.
• Explain why three states, not two. "A boolean visited flag works for undirected graphs, but directed graphs need three states to distinguish back edges from cross edges."
• Mention both approaches. "I'll use DFS with three-state coloring, but this can also be solved with BFS using Kahn's algorithm for topological sort."
• Discuss the follow-up. "Course Schedule II asks for the actual ordering. I'd modify the DFS to push nodes onto a stack after marking them visited, then reverse the stack for the topological order."

Related Problems

• Course Schedule II - Return a valid course ordering. Modify DFS to collect nodes in reverse post-order.
• Course Schedule III - Maximize courses completable within time constraints. Greedy with a max-heap.
• Alien Dictionary - Derive letter ordering from sorted alien words. Build a graph of character precedence and topological sort.
• Minimum Height Trees - Find roots that minimize tree height. Iteratively prune leaf nodes (similar to Kahn's peeling).

The cycle detection and topological sort patterns from Course Schedule carry into all dependency-ordering problems.

Ready to practice graph problems? Firecode sequences related problems using spaced repetition so you build intuition for DFS, BFS, and topological sort over time. Over 50,000 engineers have used it to prepare for interviews at top companies like Amazon, Google, and Meta.

Solutions in Other Languages

Python

from typing import List

class Solution:
    def can_finish(self, num_courses: int, prerequisites: List[List[int]]) -> bool:
        adj_list = [[] for _ in range(num_courses)]

        for dest, src in prerequisites:
            adj_list[src].append(dest)

        visit_status = [0] * num_courses

        for i in range(num_courses):
            if self._has_cycle(i, adj_list, visit_status):
                return False

        return True

    def _has_cycle(self, course: int, adj_list: List[List[int]], visit_status: List[int]) -> bool:
        if visit_status[course] == 1:
            return True
        if visit_status[course] == 2:
            return False

        visit_status[course] = 1

        for next_course in adj_list[course]:
            if self._has_cycle(next_course, adj_list, visit_status):
                return True

        visit_status[course] = 2
        return False

JavaScript

class Solution {
  canFinish(numCourses, prerequisites) {
    const adjList = Array.from({ length: numCourses }, () => []);

    for (const [course, prereq] of prerequisites) {
      adjList[prereq].push(course);
    }

    const visitStatus = Array(numCourses).fill(0);

    for (let i = 0; i < numCourses; i++) {
      if (this._hasCycle(i, adjList, visitStatus)) {
        return false;
      }
    }

    return true;
  }

  _hasCycle(course, adjList, visitStatus) {
    if (visitStatus[course] === 1) {
      return true;
    }
    if (visitStatus[course] === 2) {
      return false;
    }

    visitStatus[course] = 1;

    for (const nextCourse of adjList[course]) {
      if (this._hasCycle(nextCourse, adjList, visitStatus)) {
        return true;
      }
    }

    visitStatus[course] = 2;
    return false;
  }
}

TypeScript

class Solution {
  canFinish(numCourses: number, prerequisites: number[][]): boolean {
    const graph: number[][] = Array.from({ length: numCourses }, () => []);
    const indegree: number[] = Array(numCourses).fill(0);

    for (const [course, prereq] of prerequisites) {
      graph[prereq].push(course);
      indegree[course]++;
    }

    const queue: number[] = [];
    for (let i = 0; i < numCourses; i++) {
      if (indegree[i] === 0) {
        queue.push(i);
      }
    }

    let count = 0;
    while (queue.length > 0) {
      const current = queue.shift()!;
      count++;
      for (const neighbor of graph[current]) {
        indegree[neighbor]--;
        if (indegree[neighbor] === 0) {
          queue.push(neighbor);
        }
      }
    }

    return count === numCourses;
  }
}

C++

#include <vector>
#include <queue>

class Solution {
public:
  bool canFinish(int numCourses, std::vector<std::vector<int>> &prerequisites) {
    std::vector<std::vector<int>> adjList(numCourses);
    std::vector<int> inDegree(numCourses, 0);

    for (const auto& pair : prerequisites) {
      int course = pair[0];
      int prereq = pair[1];
      adjList[prereq].push_back(course);
      inDegree[course]++;
    }

    std::queue<int> zeroInDegreeQueue;
    for (int i = 0; i < numCourses; ++i) {
      if (inDegree[i] == 0) {
        zeroInDegreeQueue.push(i);
      }
    }

    int coursesTaken = 0;
    while (!zeroInDegreeQueue.empty()) {
      int course = zeroInDegreeQueue.front();
      zeroInDegreeQueue.pop();
      coursesTaken++;

      for (int nextCourse : adjList[course]) {
        inDegree[nextCourse]--;
        if (inDegree[nextCourse] == 0) {
          zeroInDegreeQueue.push(nextCourse);
        }
      }
    }

    return coursesTaken == numCourses;
  }
};

Go

package solution

func (s *Solution) CanFinish(numCourses int, prerequisites [][]int) bool {
    graph := make([][]int, numCourses)
    inDegree := make([]int, numCourses)

    for _, prereq := range prerequisites {
        nextCourse, prevCourse := prereq[0], prereq[1]
        graph[prevCourse] = append(graph[prevCourse], nextCourse)
        inDegree[nextCourse]++
    }

    queue := make([]int, 0)

    for i := 0; i < numCourses; i++ {
        if inDegree[i] == 0 {
            queue = append(queue, i)
        }
    }

    completedCourses := 0

    for len(queue) > 0 {
        course := queue[0]
        queue = queue[1:]
        completedCourses++

        for _, nextCourse := range graph[course] {
            inDegree[nextCourse]--
            if inDegree[nextCourse] == 0 {
                queue = append(queue, nextCourse)
            }
        }
    }

    return completedCourses == numCourses
}

Scala

class Solution {
  def canFinish(numCourses: Int, prerequisites: Array[Array[Int]]): Boolean = {
    import scala.collection.mutable

    val graph = Array.fill(numCourses)(mutable.ListBuffer[Int]())
    val indegree = Array.fill(numCourses)(0)

    for (Array(course, prereq) <- prerequisites) {
      graph(prereq) += course
      indegree(course) += 1
    }

    val queue = mutable.Queue[Int]()
    for (i <- 0 until numCourses if indegree(i) == 0) {
      queue.enqueue(i)
    }

    var count = 0
    while (queue.nonEmpty) {
      val course = queue.dequeue()
      count += 1
      for (nextCourse <- graph(course)) {
        indegree(nextCourse) -= 1
        if (indegree(nextCourse) == 0) {
          queue.enqueue(nextCourse)
        }
      }
    }

    count == numCourses
  }
}

Kotlin

class Solution {

  fun canFinish(numCourses: Int, prerequisites: Array<IntArray>): Boolean {
    val adjList = List(numCourses) { mutableListOf<Int>() }

    for (prerequisite in prerequisites) {
      adjList[prerequisite[1]].add(prerequisite[0])
    }

    val visitStatus = IntArray(numCourses)

    for (i in 0 until numCourses) {
      if (hasCycle(i, adjList, visitStatus)) {
        return false
      }
    }

    return true
  }

  private fun hasCycle(course: Int, adjList: List<List<Int>>, visitStatus: IntArray): Boolean {
    if (visitStatus[course] == 1) {
      return true
    }
    if (visitStatus[course] == 2) {
      return false
    }

    visitStatus[course] = 1

    for (nextCourse in adjList[course]) {
      if (hasCycle(nextCourse, adjList, visitStatus)) {
        return true
      }
    }

    visitStatus[course] = 2
    return false
  }
}

Swift

import Foundation

class Solution {
    func canFinish(_ numCourses: Int, _ prerequisites: [[Int]]) -> Bool {
        var adjList = Array(repeating: [Int](), count: numCourses)

        for prerequisite in prerequisites {
            adjList[prerequisite[1]].append(prerequisite[0])
        }

        var visitStatus = Array(repeating: 0, count: numCourses)

        for i in 0..<numCourses {
            if hasCycle(i, adjList, &visitStatus) {
                return false
            }
        }

        return true
    }

    private func hasCycle(_ course: Int, _ adjList: [[Int]], _ visitStatus: inout [Int]) -> Bool {
        if visitStatus[course] == 1 {
            return true
        }
        if visitStatus[course] == 2 {
            return false
        }

        visitStatus[course] = 1

        for nextCourse in adjList[course] {
            if hasCycle(nextCourse, adjList, &visitStatus) {
                return true
            }
        }

        visitStatus[course] = 2
        return false
    }
}

Rust

pub struct Solution;

impl Solution {
    pub fn can_finish(&self, num_courses: i32, prerequisites: Vec<Vec<i32>>) -> bool {
        let mut adj_list: Vec<Vec<i32>> = vec![vec![]; num_courses as usize];

        for prereq in &prerequisites {
            adj_list[prereq[1] as usize].push(prereq[0]);
        }

        let mut visit_status = vec![0i32; num_courses as usize];

        for i in 0..num_courses as usize {
            if Self::has_cycle(i, &adj_list, &mut visit_status) {
                return false;
            }
        }

        true
    }

    fn has_cycle(course: usize, adj_list: &[Vec<i32>], visit_status: &mut [i32]) -> bool {
        if visit_status[course] == 1 {
            return true;
        }
        if visit_status[course] == 2 {
            return false;
        }

        visit_status[course] = 1;

        for &next_course in &adj_list[course] {
            if Self::has_cycle(next_course as usize, adj_list, visit_status) {
                return true;
            }
        }

        visit_status[course] = 2;
        false
    }
}

C#

using System.Collections.Generic;

public class Solution {

    public bool CanFinish(int numCourses, int[][] prerequisites) {
        var adjList = new List<List<int>>();
        for (int i = 0; i < numCourses; i++) {
            adjList.Add(new List<int>());
        }

        foreach (var prerequisite in prerequisites) {
            adjList[prerequisite[1]].Add(prerequisite[0]);
        }

        var visitStatus = new int[numCourses];

        for (int i = 0; i < numCourses; i++) {
            if (HasCycle(i, adjList, visitStatus)) {
                return false;
            }
        }

        return true;
    }

    private bool HasCycle(int course, List<List<int>> adjList, int[] visitStatus) {
        if (visitStatus[course] == 1) {
            return true;
        }
        if (visitStatus[course] == 2) {
            return false;
        }

        visitStatus[course] = 1;

        foreach (var nextCourse in adjList[course]) {
            if (HasCycle(nextCourse, adjList, visitStatus)) {
                return true;
            }
        }

        visitStatus[course] = 2;
        return false;
    }
}

Dart

class Solution {
  bool canFinish(int numCourses, List<List<int>> prerequisites) {
    List<List<int>> adjList = List.generate(numCourses, (_) => []);

    for (List<int> prerequisite in prerequisites) {
      adjList[prerequisite[1]].add(prerequisite[0]);
    }

    List<int> visitStatus = List.filled(numCourses, 0);

    for (int i = 0; i < numCourses; i++) {
      if (_hasCycle(i, adjList, visitStatus)) {
        return false;
      }
    }

    return true;
  }

  bool _hasCycle(int course, List<List<int>> adjList, List<int> visitStatus) {
    if (visitStatus[course] == 1) {
      return true;
    }
    if (visitStatus[course] == 2) {
      return false;
    }

    visitStatus[course] = 1;

    for (int nextCourse in adjList[course]) {
      if (_hasCycle(nextCourse, adjList, visitStatus)) {
        return true;
      }
    }

    visitStatus[course] = 2;
    return false;
  }
}

PHP

<?php

class Solution {
    public function canFinish(int $numCourses, array $prerequisites): bool {
        $adjList = array_fill(0, $numCourses, []);

        foreach ($prerequisites as $prerequisite) {
            $adjList[$prerequisite[1]][] = $prerequisite[0];
        }

        $visitStatus = array_fill(0, $numCourses, 0);

        for ($i = 0; $i < $numCourses; $i++) {
            if ($this->hasCycle($i, $adjList, $visitStatus)) {
                return false;
            }
        }

        return true;
    }

    private function hasCycle(int $course, array &$adjList, array &$visitStatus): bool {
        if ($visitStatus[$course] === 1) {
            return true;
        }
        if ($visitStatus[$course] === 2) {
            return false;
        }

        $visitStatus[$course] = 1;

        foreach ($adjList[$course] as $nextCourse) {
            if ($this->hasCycle($nextCourse, $adjList, $visitStatus)) {
                return true;
            }
        }

        $visitStatus[$course] = 2;
        return false;
    }
}

Ruby

class Solution
  def can_finish?(num_courses, prerequisites)
    adj_list = Array.new(num_courses) { [] }

    prerequisites.each { |prereq| adj_list[prereq[1]] << prereq[0] }

    visit_status = Array.new(num_courses, 0)

    (0...num_courses).each do |i|
      return false if has_cycle?(i, adj_list, visit_status)
    end

    true
  end

  def has_cycle?(course, adj_list, visit_status)
    return true if visit_status[course] == 1

    return false if visit_status[course] == 2

    visit_status[course] = 1

    adj_list[course].each do |next_course|
      return true if has_cycle?(next_course, adj_list, visit_status)
    end

    visit_status[course] = 2

    false
  end
end