Parallel Courses

There are n courses and prerequisites (u must be taken before v). Find minimum semesters to complete all courses. Return -1 if impossible (cycle).

Example 1

Input: n=3, relations=[[1,3],[2,3]] → Output: 2

Example 2

Input: n=3, relations=[[1,2],[2,3],[3,1]] → Output: -1

Solution Approach

Topological sort with BFS (Kahn's). Track depth (semester) of each node. If not all nodes processed, there is a cycle.

Build adjacency list and in-degree array.
BFS from all nodes with in-degree 0.
Each BFS level = one semester. Decrement in-degrees of neighbors; add to queue when in-degree becomes 0.
If total processed < n: return -1 (cycle). Else return levels.

Java

import java.util.*;

class Solution {
    public int minimumSemesters(int n, int[][] relations) {
        List<List<Integer>> graph = new ArrayList<>();
        int[] inDegree = new int[n+1];
        for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
        for (int[] r : relations) { graph.get(r[0]).add(r[1]); inDegree[r[1]]++; }
        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i <= n; i++) if (inDegree[i] == 0) q.offer(i);
        int semesters = 0, studied = 0;
        while (!q.isEmpty()) {
            semesters++;
            int size = q.size(); studied += size;
            for (int i = 0; i < size; i++) {
                int u = q.poll();
                for (int v : graph.get(u)) if (--inDegree[v] == 0) q.offer(v);
            }
        }
        return studied == n ? semesters : -1;
    }
}

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