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.

In one semester, you can take any number of courses as long as you have taken all the prerequisites for the course 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.

Thinking Process

  1. Longest Path in DAG: Minimum semesters = length of longest path
    • Each node in path must be taken in sequence
    • Longest path determines minimum semesters needed
    • 0 = unvisited
  • Define state: what subproblem does dp[i] (or dp[i][j]) represent?
  • Recurrence: how does the answer build from smaller indices?
  • Base cases first; optimize space if only prior row/layer is needed.
Graph BFS layers S a b t BFS: expand by layers (queue)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
1D DP (this problem) O(n) O(n) or O(1) Linear recurrence
2D DP O(nm) O(nm) or O(n) Grid or two-sequence problems
State machine DP O(n) O(1) Buy/sell, hold/not-hold states
Memoization (top-down) Same as DP O(n) Recursive + cache

Examples

Example 1:

Input: n = 3, relations = [[1,3],[2,3]]
Output: 2
Explanation: The figure above represents the given graph.
In the first semester, you can take courses 1 and 2.
In the second semester, you can take course 3.

Example 2:

Input: n = 3, relations = [[1,2],[2,3],[3,1]]
Output: -1
Explanation: No course can be studied because there is a prerequisite cycle.

Constraints

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

Common Mistakes

  1. No prerequisites: n = 3, relations = [] → return 1 (all in one semester)
  2. Cycle exists: n = 2, relations = [[1,2],[2,1]] → return -1
  3. Linear chain: n = 4, relations = [[1,2],[2,3],[3,4]] → return 4
  4. Multiple paths: n = 3, relations = [[1,3],[2,3]] → return 2

  5. Single node: n = 1, relations = [] → return 1

  6. Not detecting cycles: Forgetting to check for -1 during DFS
  7. Wrong memoization: Not converting -1 to positive value after computation
  8. Wrong base case: Returning 0 instead of 1 for leaf nodes
  9. Not finding max: Only checking one path instead of maximum across all paths
  10. Index confusion: Using 0-indexed vs 1-indexed nodes

Alternative Approach: Topological Sort (Kahn’s Algorithm)

class Solution:
    def minimumSemesters(self, n, relations):
        graph = [[] for _ in range(n + 1)]
        
        for relation in relations:
            graph[relation[0]].append(relation[1])
        
        visited = [0] * (n + 1)
        maxLen = 1
        
        def dfs(node):
            if visited[node] != 0:
                return visited[node]
            
            visited[node] = -1
            maxLen = 1
            
            for endNode in graph[node]:
                length = dfs(endNode)
                
                if length == -1:
                    return -1
                
                maxLen = max(maxLen, length + 1)
            
            visited[node] = maxLen
            return maxLen
        
        for node in range(1, n + 1):
            length = dfs(node)
            
            if length == -1:
                return -1
            
            maxLen = max(maxLen, length)
        
        return maxLen

Time Complexity: O(V + E)
Space Complexity: O(V + E)

Key Takeaways

  1. Longest Path in DAG: Minimum semesters = length of longest path
    • Each node in path must be taken in sequence
    • Longest path determines minimum semesters needed
  2. Cycle Detection: Three-state coloring
    • 0 = unvisited
    • -1 = visiting (if encountered again, cycle exists)
    • positive = visited and memoized
  3. Memoization: Avoids recomputing longest path from each node
    • Once computed, result is cached in visited[node]
    • Significantly improves efficiency
  4. DFS Order: Process all neighbors before finalizing current node
    • Ensures we find longest path through all possible routes
  5. Base Case: Node with no outgoing edges has length 1
    • Can be taken in first semester (if no prerequisites)

References

Template Reference