LeetCode 1136 - Parallel Courses

The problem is asking us to determine the minimum number of semesters required to complete n courses given a set of prerequisite relationships.

leetcodemediumgraph-theorytopological-sort

LeetCode Problem 1136

Difficulty: 🟡 Medium
Topics: Graph Theory, Topological Sort

Solution

Problem Understanding

The problem is asking us to determine the minimum number of semesters required to complete n courses given a set of prerequisite relationships. Each course is labeled from 1 to n, and the prerequisites are described as pairs [prevCourse, nextCourse] in the relations array, meaning prevCourse must be completed before nextCourse. In a single semester, you can take as many courses as you want, provided that all their prerequisites have been completed in previous semesters.

The input consists of the number of courses n and a list of prerequisite pairs. The output is a single integer representing the minimum semesters needed to finish all courses. If it is impossible due to cyclic dependencies, the function should return -1.

Constraints tell us that n can be up to 5000, and the number of relations is also up to 5000. This rules out solutions that are exponential in n or require traversing all permutations of courses, as those would be computationally infeasible. Each pair is unique and does not contain self-dependencies.

Important edge cases include cycles in the graph, a course with no prerequisites, and disconnected subgraphs (courses that do not depend on each other). The problem guarantees valid course labels and unique prerequisite pairs, so we do not need to handle invalid inputs.

Approaches

A brute-force approach would try all possible sequences of semesters by generating all permutations of courses and checking if they respect prerequisites. This guarantees correctness because it explores every possible order, but it is infeasible for n = 5000 since the number of permutations grows factorially.

The key observation for an optimal solution is that this problem can be modeled as a directed acyclic graph (DAG), where nodes are courses and edges are prerequisites. Calculating the minimum semesters is equivalent to finding the longest path length in the DAG, since courses that depend on others must be taken after them. This naturally leads to a topological sort approach. By processing courses in order of dependencies and counting semesters, we can find the minimum number of semesters efficiently.

Approach Time Complexity Space Complexity Notes
Brute Force O(n!) O(n) Generate all course orders and check prerequisites, infeasible for large n
Optimal O(n + m) O(n + m) Topological sort using BFS (Kahn’s algorithm) to count semesters, scalable to given constraints

Algorithm Walkthrough

  1. Construct a graph representation using an adjacency list where each course maps to the list of courses that depend on it. Maintain an array in_degree to track the number of prerequisites for each course.
  2. Initialize a queue with courses that have zero prerequisites (in-degree 0). These courses can be taken in the first semester.
  3. Initialize a counter semester = 0. While the queue is not empty, increment the semester. For each course in the current semester, remove it from the graph and reduce the in-degree of its dependent courses. If a dependent course’s in-degree becomes zero, add it to the queue for the next semester.
  4. Keep track of the number of courses processed. After the BFS completes, if all courses have been processed, return the semester count. Otherwise, if there are courses left unprocessed, it indicates a cycle, so return -1.

Why it works: The BFS topological sort ensures that a course is only taken after all its prerequisites are completed. Each BFS level represents a semester, so counting levels gives the minimum number of semesters. The in-degree array guarantees that no course is processed before its prerequisites, preventing invalid sequences.

Python Solution

from collections import deque
from typing import List

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

        for prev_course, next_course in relations:
            graph[prev_course].append(next_course)
            in_degree[next_course] += 1

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

        while queue:
            semester += 1
            for _ in range(len(queue)):
                course = queue.popleft()
                processed += 1
                for neighbor in graph[course]:
                    in_degree[neighbor] -= 1
                    if in_degree[neighbor] == 0:
                        queue.append(neighbor)

        return semester if processed == n else -1

This code constructs the adjacency list and in-degree array, initializes the BFS queue with courses having zero prerequisites, and processes each level as a semester. It ensures that a course is only taken when all prerequisites are satisfied. If a cycle exists, the number of processed courses will be less than n, and -1 is returned.

Go Solution

package main

func minimumSemesters(n int, relations [][]int) int {
    graph := make([][]int, n+1)
    inDegree := make([]int, n+1)
    
    for _, rel := range relations {
        prev, next := rel[0], rel[1]
        graph[prev] = append(graph[prev], next)
        inDegree[next]++
    }
    
    queue := []int{}
    for i := 1; i <= n; i++ {
        if inDegree[i] == 0 {
            queue = append(queue, i)
        }
    }
    
    semester := 0
    processed := 0
    
    for len(queue) > 0 {
        semester++
        size := len(queue)
        nextQueue := []int{}
        for i := 0; i < size; i++ {
            course := queue[i]
            processed++
            for _, neighbor := range graph[course] {
                inDegree[neighbor]--
                if inDegree[neighbor] == 0 {
                    nextQueue = append(nextQueue, neighbor)
                }
            }
        }
        queue = nextQueue
    }
    
    if processed == n {
        return semester
    }
    return -1
}

The Go solution mirrors the Python logic with slices instead of deques. We carefully track the queue for BFS by creating a nextQueue to avoid modifying the slice while iterating.

Worked Examples

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

Semester Queue Processed Courses Notes
1 [1,2] 2 Courses 1 and 2 have no prerequisites
2 [3] 3 Course 3 becomes available after 1 and 2 are done

Return 2 semesters.

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

Queue starts empty because all courses have in-degree > 0 due to cycle. processed = 0 < 3, so return -1.

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) We visit each course once and process each edge once during BFS
Space O(n + m) Adjacency list stores all edges, in-degree array stores n values, queue can store up to n courses

The BFS topological sort is linear with respect to nodes and edges, making it efficient for the given constraints.

Test Cases

# Provided examples
assert Solution().minimumSemesters(3, [[1,3],[2,3]]) == 2  # Basic DAG
assert Solution().minimumSemesters(3, [[1,2],[2,3],[3,1]]) == -1  # Cycle detection

# Edge cases
assert Solution().minimumSemesters(1, []) == 1  # Single course, no prerequisites
assert Solution().minimumSemesters(4, [[1,2],[2,3],[3,4]]) == 4  # Linear chain of prerequisites
assert Solution().minimumSemesters(4, [[1,2],[1,3],[2,4],[3,4]]) == 3  # Diamond shape dependencies
assert Solution().minimumSemesters(5, []) == 1  # Multiple independent courses
Test Why
n=3, relations=[[1,3],[2,3]] Simple DAG with shared dependency
n=3, relations=[[1,2],[2,3],[3,1]] Cycle detection
n=1, relations=[] Minimal input
n=4, linear chain Ensures sequential processing is counted
n=4, diamond shape Multiple dependencies converge
n=5, no relations Independent courses can be taken in one semester

Edge Cases

A key edge case is a cycle in the graph. If a cycle exists, no topological sort is possible, and the BFS queue will become empty before processing all courses. The algorithm correctly returns -1 in this case.

Another edge case is independent courses. If multiple courses have no prerequisites, they can all be taken in the same semester. Our BFS implementation naturally handles this by initializing the queue with all courses having zero in-degree.

A final edge case is a linear chain of prerequisites. If every course depends on the previous one, each course must be taken in a separate semester. BFS correctly increments the semester