☕ DSA Java Articles

Topics › Graphs › Topo Sort and Problems

Course Schedule I

Hard TUF ID 504 A2ZBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

There are numCourses courses labelled 0 to numCourses - 1. You are given a list prerequisites where {a, b} means “to take course a you must first finish course b”. Return true if it is possible to finish every course, and false otherwise.

Constraints: 1 ≤ numCourses ≤ 2000, 0 ≤ prerequisites.length ≤ 5000, all pairs refer to valid courses. Pairs may repeat, and a pair may even name the same course twice.

Example 1

numCourses = 2, prerequisites = [[1, 0]]
answer = true            // take 0, then 1

Example 2

numCourses = 2, prerequisites = [[1, 0], [0, 1]]
answer = false           // 1 waits for 0 and 0 waits for 1, so neither can start

Modelling. Make each course a node and draw an edge b → a for each pair {a, b}: “finishing b unlocks a”. A valid schedule is an ordering of the nodes in which every edge points forward, a topological order. Such an order exists exactly when the graph has no directed cycle. So the question “can every course be finished?” is the question “is this directed graph acyclic?”.

static List<List<Integer>> buildGraph(int numCourses, int[][] prerequisites) {
    List<List<Integer>> 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]);
    return adj;
}

Approach 1: Brute force, simulate semesters

Intuition. Do what a student would do. Each semester, look at every course you have not taken and take it if all of its prerequisites are already done. Repeat. If you ever reach a semester where courses remain but none of them can be taken, you are stuck forever, because nothing will change next semester either.

Why does “stuck” mean a cycle? Every remaining course has at least one prerequisite that is also remaining. Start at any remaining course and keep jumping to one of its unfinished prerequisites. There are finitely many courses, so you must eventually revisit one: that is a cycle of courses each waiting for the next.

Algorithm.

  1. Keep a taken array and a counter.
  2. Each round, mark a course blocked if any of its prerequisites is not yet taken (one scan over all pairs).
  3. Take every course that is neither taken nor blocked.
  4. If the round took nothing, return false. If all courses are taken, return true.
static boolean bruteForce(int numCourses, int[][] prerequisites) {
    boolean[] taken = new boolean[numCourses];
    int takenCount = 0;
    while (takenCount < numCourses) {
        boolean[] blocked = new boolean[numCourses];
        for (int[] p : prerequisites) {
            if (!taken[p[1]]) blocked[p[0]] = true;       // course p[0] still waits for p[1]
        }
        int before = takenCount;
        for (int c = 0; c < numCourses; c++) {
            if (!taken[c] && !blocked[c]) {
                taken[c] = true;
                takenCount++;
            }
        }
        if (takenCount == before) return false;           // nothing could be taken this semester: stuck on a cycle
    }
    return true;
}

The blocked array is computed before anything is taken in a round, so a course and its prerequisite are never taken in the same semester. That keeps the simulation honest, although for this yes/no question taking them in one round would also give the right answer.

Complexity. Time O(V × (V + E)): each round scans all E pairs and all V courses, and a long chain forces V rounds because only one course becomes available each time. Space O(V) for the two boolean arrays.

Approach 2: DFS with three colours

Intuition. Since the question is cycle detection, use the DFS cycle test. Instead of two boolean arrays (visited and on-path) we can store one state per course:

Reaching a state-1 course means we followed edges back to a course that is still waiting for this very search to finish, which is a cycle. Reaching a state-2 course is harmless and needs no further work, because that course was already proven cycle-free.

Algorithm.

  1. For every course with state 0, run hasCycle.
  2. In hasCycle(u): set state 1, then for each neighbour v return true if v is in state 1, or if v is in state 0 and its own search finds a cycle.
  3. Set state 2 and return false.
static boolean dfsThreeColour(int numCourses, int[][] prerequisites) {
    List<List<Integer>> adj = buildGraph(numCourses, prerequisites);
    int[] state = new int[numCourses];                    // 0 = unvisited, 1 = on current path, 2 = finished
    for (int c = 0; c < numCourses; c++) {
        if (state[c] == 0 && hasCycle(c, adj, state)) return false;
    }
    return true;
}

static boolean hasCycle(int u, List<List<Integer>> adj, int[] state) {
    state[u] = 1;
    for (int v : adj.get(u)) {
        if (state[v] == 1) return true;
        if (state[v] == 0 && hasCycle(v, adj, state)) return true;
    }
    state[u] = 2;
    return false;
}

Complexity. Time O(V + E): each course is expanded once, after which it is in state 2 forever. Space O(V + E) for the graph, plus the state array and up to V levels of recursion.

Approach 3: Optimal, Kahn’s algorithm

Intuition. Look again at the semester simulation. Its waste is that every round rescans all prerequisite pairs to discover which courses became free. But a course can only become free at the moment one of its prerequisites is finished. So keep, for each course, a counter of unfinished prerequisites (its in-degree). When a course is finished, decrement the counter of each course it unlocks, and the courses whose counter hits zero are exactly the newly available ones. That is Kahn’s topological sort, and it is the brute force with the rescanning removed.

The final check is the same as in the simulation: if every course was eventually finished, a schedule exists. Courses on a cycle never reach a zero counter, because each one waits for its predecessor on the cycle.

Algorithm.

  1. Build the graph and compute indegree[a] = number of pairs {a, _}.
  2. Queue every course with in-degree 0.
  3. Pop a course, count it as finished, and decrement each dependent; queue any that reach 0.
  4. Return finished == numCourses.
static boolean optimal(int numCourses, int[][] prerequisites) {
    List<List<Integer>> adj = buildGraph(numCourses, prerequisites);
    int[] indegree = new int[numCourses];                 // number of unfinished prerequisites
    for (int[] p : prerequisites) indegree[p[0]]++;
    Deque<Integer> queue = new ArrayDeque<>();
    for (int c = 0; c < numCourses; c++) if (indegree[c] == 0) queue.add(c);
    int finished = 0;
    while (!queue.isEmpty()) {
        int u = queue.poll();
        finished++;
        for (int v : adj.get(u)) {
            if (--indegree[v] == 0) queue.add(v);
        }
    }
    return finished == numCourses;
}

Dry run on numCourses = 5, prerequisites = [[1,0], [2,0], [3,1], [3,2], [4,3]] (edges 0→1, 0→2, 1→3, 2→3, 3→4):

pop finished in-degrees (0..4) after the pop queue after
start 0 0, 1, 1, 2, 1 [0]
0 1 0, 0, 0, 2, 1 [1, 2]
1 2 0, 0, 0, 1, 1 [2]
2 3 0, 0, 0, 0, 1 [3]
3 4 0, 0, 0, 0, 0 [4]
4 5 0, 0, 0, 0, 0 []

All five courses were finished, so the answer is true. Add the pair [1, 3] and course 1 would start with in-degree 2. After popping 0 and 2 it still waits for 3, which waits for 1, and the run would stop at finished = 2, short of 5.

Complexity. Time O(V + E): each course is queued at most once and each pair is decremented once. Space O(V + E) for the adjacency list, in-degrees and the queue.

Both Approach 2 and Approach 3 are linear. Kahn’s version is iterative, so a chain of 2000 courses cannot overflow the call stack, and the same loop gives you the actual schedule if you record the popped order, which is the follow-up problem.

Edge cases and pitfalls