Parallel Courses Python Solution with Tests

Tested Python solution for LeetCode 1136 with 26 pytest cases. Generate a practice environment with lcpy.

LeetCode 1136, Medium. Topics: Graph, Topological Sort. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 26 parametrized pytest cases, and a playground notebook:

lcpy gen -n 1136   # by problem number
lcpy gen -s parallel_courses   # by problem name

​

Problem

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 taken before course nextCourse_i.

In one semester, you can take any number of courses as long as you have taken all the prerequisites in the previous semester for the courses you are taking.

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

​

Examples

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

Explanation: In the first semester, you can take courses 1 and 2. In the second semester, you can take course 3.

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

Explanation: No course can be studied because they are prerequisites of each other.

​

Constraints

• 1 <= n <= 5000
• 1 <= relations.length <= 5000
• relations[i].length == 2
• 1 <= prevCourse_i, nextCourse_i <= n
• prevCourse_i != nextCourse_i
• All the pairs [prevCourse_i, nextCourse_i] are unique.

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

from collections import deque


class Solution:
    # Time: O(n + m)
    # Space: O(n + m)
    def minimum_semesters(self, n: int, relations: list[list[int]]) -> int:
        graph: list[list[int]] = [[] for _ in range(n)]
        indegree = [0] * n
        for prev_course, next_course in relations:
            graph[prev_course - 1].append(next_course - 1)
            indegree[next_course - 1] += 1

        queue: deque[int] = deque(i for i in range(n) if indegree[i] == 0)
        semesters = 0
        taken = 0
        while queue:
            semesters += 1
            for _ in range(len(queue)):
                course = queue.popleft()
                taken += 1
                for nxt in graph[course]:
                    indegree[nxt] -= 1
                    if indegree[nxt] == 0:
                        queue.append(nxt)
        return semesters if taken == n else -1

​

Complexity

Time	Space
O(n + m)	O(n + m)

​

Tags

NeetCode All.