LeetCode · #1136

Parallel Courses Solution

Given n courses and prerequisite relations, return the minimum number of semesters needed to finish everything if you can take any number of currently unlocked courses in the same semester.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #1136

🏗️

Pattern

Topological sort — BFS levels

Each relation [prev, next] means course prev must be taken before course next. In one semester you may take every course whose prerequisites are already satisfied. Return the minimum number of semesters, or -1 if a cycle makes completion impossible.

Example

Input:  n = 3, relations = [[1,3],[2,3]]
Output: 2
// Semester 1: take 1 and 2
// Semester 2: take 3

Constraints

• 1 ≤ n ≤ 5000
• 1 ≤ relations.length ≤ 5000
• relations[i] = [prev, next]
• Courses are labeled 1..n

Section Two · Approach 1

Repeated Scanning of Prerequisites — O(n · m)

One naive approach is to simulate semesters directly: in every semester, scan all courses and all relations to find which courses are now available. Mark them taken, then repeat until no progress is made.

Why it works

Any course becomes available exactly when all its prerequisite courses have been marked complete. Repeating this semester by semester eventually finishes all reachable courses.

Problem: We keep rescanning the same edges every semester even when nothing about most courses changed. That wastes work. Kahn's algorithm keeps an in-degree count so each edge is processed once, exactly when its prerequisite course is completed.

Idea sketch

for each semester:
  find all untaken courses whose prerequisites are all satisfied
  if none exist before all courses are taken: cycle → return -1
  mark all of them taken together

Section Three · Approach 2

Kahn's Topological BFS by Levels — O(V + E)

Build the directed graph and compute inDegree[next] for every course. All courses with in-degree 0 can be taken immediately, so they form semester 1. Pop the current queue size as one BFS layer, reduce neighbors' in-degrees, and any neighbor reaching 0 joins the next semester.

💡 Mental model: Think of each course as having a lock counter equal to its number of unfinished prerequisites. Every semester, you take all currently unlocked courses. Finishing a course removes one lock from each dependent course. When a dependent course's counter drops to zero, it unlocks for the next semester.

Build adjacency list prev → next.
Compute all in-degrees.
Seed the queue with every course having in-degree 0.
Each BFS layer = one semester.
If processed courses < n after BFS ends, a cycle exists → return -1.

Recognition signal:

When the prompt says minimum number of rounds / semesters / phases under prerequisite constraints, think topological sort + level-order processing.
The BFS layer count is the answer.

Section Four · Trace

Visual Walkthrough

Trace n = 3, relations = [[1,3],[2,3]].

Parallel Courses — semester layering

Section Five · Implementation

Code — Java & Python

Java — Kahn's BFS with semester levels

import java.util.*;

class Solution {
    public int minimumSemesters(int n, int[][] relations) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());

        int[] inDegree = new int[n + 1];
        for (int[] edge : relations) {
            int prev = edge[0], next = edge[1];
            adj.get(prev).add(next);
            inDegree[next]++;
        }

        Queue<Integer> queue = new ArrayDeque<>();
        for (int course = 1; course <= n; course++) {
            if (inDegree[course] == 0) queue.offer(course);
        }

        int semesters = 0, processed = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            semesters++;
            for (int i = 0; i < size; i++) {
                int course = queue.poll();
                processed++;
                for (int next : adj.get(course)) {
                    if (--inDegree[next] == 0) queue.offer(next);
                }
            }
        }

        return processed == n ? semesters : -1;
    }
}

Python — BFS layering

from collections import deque

class Solution:
    def minimumSemesters(self, n: int, relations: list[list[int]]) -> int:
        adj = [[] for _ in range(n + 1)]
        indegree = [0] * (n + 1)

        for prev, nxt in relations:
            adj[prev].append(nxt)
            indegree[nxt] += 1

        queue = deque(course for course in range(1, n + 1) if indegree[course] == 0)
        semesters = 0
        processed = 0

        while queue:
            semesters += 1
            for _ in range(len(queue)):
                course = queue.popleft()
                processed += 1
                for nxt in adj[course]:
                    indegree[nxt] -= 1
                    if indegree[nxt] == 0:
                        queue.append(nxt)

        return semesters if processed == n else -1

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Repeated semester scanning	O(n · m)	O(n)	Simple simulation, but rescans relations too often.
Kahn's BFS ← optimal	O(V + E)	O(V + E)	Each edge is processed once, and BFS levels directly equal semesters.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Expected behavior	Why it matters
No relations	Return `1` when n > 0	All courses are available immediately in semester 1.
Simple chain	`1→2→3` returns 3	Each semester unlocks exactly one next course.
Wide layer	Take all zero-indegree courses together	You can take unlimited unlocked courses per semester.
Cycle	Return `-1`	Some courses never reach indegree 0.
Wrong semester count	Count BFS layers, not nodes	The answer is rounds, not processed courses.

⚠ Common Mistake: Incrementing the semester counter every time you pop a course. That counts courses, not rounds. Increment once per queue layer, because one layer represents all courses taken in the same semester.

← Back to Topological Sort

LearningTree

LC 1136 · Parallel Courses — Solution & Explanation | DSA Guide