Problem 23.3 · Cycle DetectionMedium

Course Schedule

PatternTopological Sort Graph DFS and Flood Fill

What it teaches: Can all tasks finish? Only if the dependency graph has no directed cycle.

Practise it on judges as “Course Schedule”.

The problem

There are numCourses courses. 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

Constraints

1 ≤ numCourses ≤ 2000
0 ≤ prerequisites ≤ 5000

Pattern clues in the wording

→ Dependencies
→ "Is it possible to finish"

These clues point to Topological Sort: Order the nodes of a directed graph so every edge goes from earlier to later, by repeatedly taking nodes with no remaining prerequisites.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        return false;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	numCourses = 2 prerequisites = [[1,0]]	true
2	numCourses = 2 prerequisites = [[1,0],[0,1]]	false

+ 2 hidden tests the code runner will check

From slow to fast

Approaches

1. Three-colour DFS · O(V + E)2. Kahn's algorithm · O(V + E)

Three-colour DFS

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

Build b → a edges. DFS from every white node; an edge into a grey node means a cycle.

Approach 1

import java.util.*;

class Solution {
    private List<List<Integer>> adj;
    private int[] state;   // 0 white, 1 grey, 2 black

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
        for (int[] p : prerequisites) adj.get(p[1]).add(p[0]);
        state = new int[numCourses];
        for (int i = 0; i < numCourses; i++) if (state[i] == 0 && hasCycle(i)) return false;
        return true;
    }

    private boolean hasCycle(int u) {
        state[u] = 1;
        for (int v : adj.get(u)) {
            if (state[v] == 1) return true;
            if (state[v] == 0 && hasCycle(v)) return true;
        }
        state[u] = 2;
        return false;
    }
}

Verdict: Direct cycle detection.

Kahn's algorithm

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

Count in-degrees; queue courses with none; take one, decrement its successors, queue new zeros. All courses taken ⇔ no cycle.

Approach 2

import java.util.*;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
        int[] indeg = new int[numCourses];
        for (int[] p : prerequisites) { adj.get(p[1]).add(p[0]); indeg[p[0]]++; }
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) q.offer(i);
        int taken = 0;
        while (!q.isEmpty()) {
            int u = q.poll();
            taken++;
            for (int v : adj.get(u)) if (--indeg[v] == 0) q.offer(v);
        }
        return taken == numCourses;
    }
}

Verdict: Iterative; also produces an order (Course Schedule II).

Before you submit

Edge cases and common mistakes

Test these inputs

No prerequisites
Self-prerequisite [a, a]
Several separate components

Mistakes people make

Using a plain visited flag in directed DFS.
Reversing the edge direction inconsistently.

Interview

Follow-up questions

How do you return a valid order?

Command Palette