Parallel Courses — LeetCode 1136 Python Solution

The 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] = [prevCoursei, nextCoursei], representing a prerequisite relationship between course prevCoursei and course nextCoursei: course prevCoursei has to be taken before course nextCoursei.

Example

Input

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

Output

2

Explanation

The figure above represents the given graph.

Python solution

class Solution:
    def minimumSemesters(self, n: int, relations: List[List[int]]) -> int:
        g = defaultdict(list)
        indeg = [0] * n
        for prev, nxt in relations:
            prev, nxt = prev - 1, nxt - 1
            g[prev].append(nxt)
            indeg[nxt] += 1
        q = deque(i for i, v in enumerate(indeg) if v == 0)
        ans = 0
        while q:
            ans += 1
            for _ in range(len(q)):
                i = q.popleft()
                n -= 1
                for j in g[i]:
                    indeg[j] -= 1
                    if indeg[j] == 0:
                        q.append(j)
        return -1 if n else ans

Complexity

Pattern: Topological Sort

Order a set of tasks so that every dependency comes before the thing that needs it. LeetCode 1136. Parallel Courses is filed here because LeetCode tags it Topological Sort, which is the vocabulary this hub collects.

The topological sort guide has the Python template for the pattern and the 32 LeetCode problems that use it.

Related problems