Skip to main content

1136 - Parallel Courses

Difficulty: Medium | Pattern: Topological Sort (BFS / Kahn's Algorithm) | Company tags: Google, Amazon, Microsoft

Problem Statement​

You are given an integer n, which indicates that there are n courses labeled from 1 to n. You are also given an array relations where relations[i] = [prevCourse_i, nextCourse_i], representing a prerequisite relationship between course prevCourse_i and course nextCourse_i: course prevCourse_i has to be studied before course nextCourse_i.

In one semester, you can study any number of courses as long as you have met all the prerequisites.

Return the minimum number of semesters needed to study all courses. If there is no way to study all courses, return -1.

Example 1:

Input: n = 3, relations = [[1,3],[2,3]]
Output: 2
Explanation: 
  Semester 1: Take courses 1 and 2
  Semester 2: Take course 3

Example 2:

Input: n = 3, relations = [[1,2],[2,3],[3,1]]
Output: -1  (cycle detected)

Algorithm Flow​

Approach: BFS Topological Sort (Kahn's) — O(V+E)​

Key insight: Use BFS level-by-level processing. Each BFS level = one semester. Courses with in-degree 0 can be taken in the current semester. After taking them, decrement the in-degree of dependent courses.

from collections import deque

def minimumSemesters(n: int, relations: list[list[int]]) -> int:
    graph = [[] for _ in range(n + 1)]
    in_degree = [0] * (n + 1)
    
    for prev, next_course in relations:
        graph[prev].append(next_course)
        in_degree[next_course] += 1
    
    # Start with all courses that have no prerequisites
    queue = deque(i for i in range(1, n + 1) if in_degree[i] == 0)
    semesters = 0
    courses_taken = 0
    
    while queue:
        semesters += 1
        # Take all available courses this semester
        for _ in range(len(queue)):
            course = queue.popleft()
            courses_taken += 1
            for neighbor in graph[course]:
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)
    
    return semesters if courses_taken == n else -1

Dry Run​

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

  • Build graph: 1→3, 2→3; in_degree: [0, 0, 0, 2] (course 3 has 2 prereqs)
  • Initial queue: [1, 2] (in_degree 0)
  • Semester 1: take 1 and 2 → in_degree[3] = 2-1-1 = 0 → queue = [3]
  • Semester 2: take 3 → courses_taken = 3 = n

Return 2 ✓

Cycle Detection​

If courses_taken < n after BFS, there's a cycle. Courses in the cycle never reach in-degree 0, so they're never enqueued.

Edge Cases​

  • relations = [] → all courses independent → 1 semester (all in parallel)
  • Linear chain 1→2→3→...→n → n semesters
  • Cycle → return -1
  • Disconnected graph (no relations between some components) → max depth across components

Complexity​

  • Time: O(V + E) where V = n (courses), E = len(relations)
  • Space: O(V + E) for adjacency list and in-degree array

Related problems: LeetCode 207 (Course Schedule — just detect cycle), LeetCode 210 (Course Schedule II — return ordering), LeetCode 1136 (this — count layers).

Key Terms​

TermDefinition
Topological sortAn ordering of a directed graph's nodes such that every edge points from an earlier node to a later one; only possible for DAGs.
Kahn's algorithmA BFS-based topological sort that repeatedly removes nodes with in-degree 0.
In-degreeThe number of incoming edges (unfinished prerequisites) a node currently has.
BFS level / semesterOne full round of processing all currently-available nodes at once, used here to model "one semester."
Cycle detectionIdentifying that not all nodes can be processed because some form a circular dependency, indicated by courses_taken < n.

FAQ​

  1. Can this be solved without extra space? No — you need at least O(V+E) for the adjacency list and in-degree array; this is unavoidable for graph traversal problems.
  2. What if the input graph has a cycle? Nodes in the cycle never reach in-degree 0, so they're never enqueued; the algorithm detects this by checking courses_taken == n at the end and returns -1 otherwise.
  3. What if we only needed to know whether all courses can be finished (not minimum semesters)? That's LeetCode 207 (Course Schedule) — same in-degree BFS, but you just check reachability of all nodes, no need to count levels.
  4. How would this change if we needed the actual course ordering rather than semester count? That's LeetCode 210 (Course Schedule II) — same Kahn's algorithm, but append each dequeued node to a result list instead of counting levels.
  5. Could DFS be used instead of BFS here? DFS-based topological sort (with a visited/visiting/done coloring) can also detect cycles and produce an ordering, but computing "minimum semesters" is more natural with BFS since each level maps directly to a semester.

Quick Revision​

  • Problem: minimum semesters to finish all courses given prerequisite pairs, or -1 if impossible.
  • Build a directed graph and an in-degree array from relations.
  • Initialize the queue with all nodes that have in-degree 0 (no prerequisites).
  • Process the queue level by level — each level = one semester.
  • For each node processed, decrement in-degree of its neighbors; enqueue any that reach 0.
  • Count total courses taken; if it's less than n, a cycle exists — return -1.
  • Time: O(V + E); Space: O(V + E).
  • This is Kahn's algorithm with level-batching instead of single-node dequeuing.
  • Pattern: Topological Sort / Kahn's Algorithm, also seen in "Course Schedule" (LeetCode 207) and "Course Schedule II" (LeetCode 210).
  • Both LeetCode 207 and 210 share the same in-degree/BFS graph traversal core as this problem.