Problem Description

You have n courses numbered from 1 to n that you need to take. Some courses have prerequisites - you must complete certain courses before you can take others.

The prerequisite relationships are given as an array relations, where each element relations[i] = [prevCoursei, nextCoursei] means you must complete course prevCoursei before taking course nextCoursei.

In each semester, you can take as many courses as you want, as long as you've already completed all their prerequisites in previous semesters.

Your task is to find the minimum number of semesters needed to complete all n courses. If it's impossible to complete all courses (for example, due to circular dependencies), return -1.

Example scenarios:

• If you have 3 courses and course 1 must be taken before course 2, and course 2 before course 3, you'd need 3 semesters (one course per semester due to the chain of dependencies).
• If you have 3 courses where course 1 must be taken before both courses 2 and 3, you'd need 2 semesters (take course 1 in semester 1, then courses 2 and 3 together in semester 2).
• If there's a circular dependency (course 1 requires course 2, and course 2 requires course 1), it's impossible to complete all courses, so return -1.

The solution uses topological sorting with BFS to process courses level by level, where each level represents one semester. Courses with no prerequisites can be taken immediately, and as courses are completed, they unlock other courses for future semesters.

Intuition

The key insight is to recognize this as a graph problem where courses are nodes and prerequisites form directed edges. We need to find the longest path from any starting course to its final dependent course - this represents the minimum number of semesters needed.

Think about how you'd naturally plan your course schedule: you'd first identify all courses with no prerequisites - these can be taken immediately in semester 1. After completing these courses, some new courses become available (their prerequisites are now satisfied). These newly available courses can be taken in semester 2, and so on.

This naturally leads us to a level-by-level processing approach, which is essentially BFS on a directed acyclic graph (DAG). Each "level" in our BFS traversal represents one semester.

The challenge is detecting if it's impossible to complete all courses. This happens when there's a cycle in the prerequisite relationships - for example, if course A requires B, B requires C, and C requires A. In such cases, none of these courses can ever be taken.

We can detect this using topological sorting with in-degrees. The idea is:

1. Track how many prerequisites each course has (in-degree)
2. Start with courses that have zero prerequisites (in-degree = 0)
3. As we "complete" each course, we reduce the in-degree of courses that depend on it
4. When a course's in-degree reaches 0, it becomes available for the next semester
5. If we process all courses this way, we can complete them all; if some courses remain unprocessed (their in-degree never reached 0), there must be a cycle

The number of "rounds" of BFS (where each round processes all currently available courses) equals the minimum number of semesters needed.

Learn more about Graph and Topological Sort patterns.

Solution Approach

The solution implements topological sorting using BFS (Kahn's algorithm) to determine the minimum number of semesters needed.

Step 1: Build the graph and calculate in-degrees

g = defaultdict(list)
indeg = [0] * n
for prev, nxt in relations:
    prev, nxt = prev - 1, nxt - 1  # Convert to 0-indexed
    g[prev].append(nxt)
    indeg[nxt] += 1

• Create an adjacency list g to represent the prerequisite relationships
• Maintain an indeg array where indeg[i] counts how many prerequisites course i has
• Convert course numbers from 1-indexed to 0-indexed for easier array manipulation

Step 2: Initialize the queue with courses having no prerequisites

q = deque(i for i, v in enumerate(indeg) if v == 0)

• Find all courses with in-degree 0 (no prerequisites)
• These courses can be taken in the first semester

Step 3: Process courses level by level (semester by semester)

ans = 0
while q:
    ans += 1  # Start a new semester
    for _ in range(len(q)):  # Process all courses available this semester
        i = q.popleft()
        n -= 1  # One course completed
        for j in g[i]:
            indeg[j] -= 1
            if indeg[j] == 0:
                q.append(j)

• Each iteration of the outer while loop represents one semester
• The inner for loop processes all courses that can be taken in the current semester
• For each completed course i:
  • Decrement n to track remaining courses
  • Reduce the in-degree of all courses that depend on i
  • If any course's in-degree becomes 0, it's available for the next semester

Step 4: Check if all courses were completed

return -1 if n else ans

• If n > 0, some courses couldn't be completed (cycle exists), return -1
• Otherwise, return ans - the number of semesters needed

The time complexity is O(V + E) where V is the number of courses and E is the number of prerequisite relationships. The space complexity is O(V + E) for storing the graph and in-degree array.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Example Input:

• n = 5 courses (numbered 1 to 5)
• relations = [[1,3], [2,3], [3,4], [3,5]]

This means:

• Course 1 must be taken before Course 3
• Course 2 must be taken before Course 3
• Course 3 must be taken before Course 4
• Course 3 must be taken before Course 5

Step 1: Build the graph and calculate in-degrees

After converting to 0-indexed and building our data structures:

• Graph g:
  • 0 → [2] (Course 1 → Course 3)
  • 1 → [2] (Course 2 → Course 3)
  • 2 → [3, 4] (Course 3 → Courses 4, 5)
• In-degrees indeg = [0, 0, 2, 1, 1]
  • Courses 1 and 2: no prerequisites (in-degree = 0)
  • Course 3: requires Courses 1 and 2 (in-degree = 2)
  • Courses 4 and 5: each requires Course 3 (in-degree = 1)

Step 2: Initialize queue with courses having no prerequisites

Queue q = [0, 1] (Courses 1 and 2 can be taken immediately)

Step 3: Process semester by semester

Semester 1 (ans = 1):

• Process Course 0 (Course 1):
  • Remove from queue, decrement n to 4
  • Update Course 2's in-degree: 2 - 1 = 1
• Process Course 1 (Course 2):
  • Remove from queue, decrement n to 3
  • Update Course 2's in-degree: 1 - 1 = 0
  • Course 2's in-degree is now 0, add to queue
• Queue after Semester 1: [2]

Semester 2 (ans = 2):

• Process Course 2 (Course 3):
  • Remove from queue, decrement n to 2
  • Update Course 3's in-degree: 1 - 1 = 0
  • Update Course 4's in-degree: 1 - 1 = 0
  • Both Courses 3 and 4 now have in-degree 0, add to queue
• Queue after Semester 2: [3, 4]

Semester 3 (ans = 3):

• Process Course 3 (Course 4):
  • Remove from queue, decrement n to 1
• Process Course 4 (Course 5):
  • Remove from queue, decrement n to 0
• Queue after Semester 3: empty

Step 4: Check completion

Since n = 0 (all courses completed), return ans = 3.

Final Schedule:

• Semester 1: Take Courses 1 and 2 (in parallel)
• Semester 2: Take Course 3
• Semester 3: Take Courses 4 and 5 (in parallel)

The algorithm correctly identifies that we need 3 semesters minimum, taking advantage of parallelism where possible while respecting prerequisite constraints.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + m)

The algorithm performs a topological sort using BFS (Kahn's algorithm). Breaking down the operations:

• Building the adjacency list g and calculating in-degrees requires iterating through all m relations: O(m)
• Finding initial nodes with zero in-degree requires scanning all n nodes: O(n)
• The BFS traversal visits each node exactly once and processes each edge exactly once when updating in-degrees: O(n + m)

Therefore, the overall time complexity is O(n + m).

Space Complexity: O(n + m)

The space usage consists of:

• The adjacency list g stores all edges, requiring O(m) space
• The indeg array stores in-degrees for all nodes: O(n)
• The queue q can contain at most n nodes: O(n)

Therefore, the overall space complexity is O(n + m).

Here, n represents the number of courses and m represents the number of prerequisite relationships (edges in the directed graph).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Convert Between 1-indexed and 0-indexed

The most common pitfall in this problem is mishandling the indexing conversion. The input courses are numbered from 1 to n (1-indexed), but arrays in most programming languages are 0-indexed.

Incorrect Implementation:

# WRONG: Using 1-indexed directly with 0-indexed arrays
indeg = [0] * n
for prev, nxt in relations:
    g[prev].append(nxt)  # This will cause index out of bounds when prev or nxt equals n
    indeg[nxt] += 1      # Array indices go from 0 to n-1, not 1 to n

Correct Implementation:

# CORRECT: Convert to 0-indexed before using as array indices
indeg = [0] * n
for prev, nxt in relations:
    prev, nxt = prev - 1, nxt - 1  # Convert from 1-indexed to 0-indexed
    g[prev].append(nxt)
    indeg[nxt] += 1

2. Not Processing All Courses in Current Semester Before Moving to Next

Another pitfall is incorrectly counting semesters by not properly batching courses that can be taken simultaneously.

Incorrect Implementation:

# WRONG: This counts each course as a separate semester
ans = 0
while q:
    i = q.popleft()
    ans += 1  # Incrementing for each course instead of each level
    n -= 1
    for j in g[i]:
        indeg[j] -= 1
        if indeg[j] == 0:
            q.append(j)

Correct Implementation:

# CORRECT: Process all courses available in current semester together
ans = 0
while q:
    ans += 1  # Increment once per semester
    for _ in range(len(q)):  # Process ALL courses available this semester
        i = q.popleft()
        n -= 1
        for j in g[i]:
            indeg[j] -= 1
            if indeg[j] == 0:
                q.append(j)

3. Using Wrong Data Structure for Queue Operations

Using a regular list instead of deque can lead to inefficient operations.

Inefficient Implementation:

# INEFFICIENT: Using list with pop(0) is O(n) operation
q = [i for i, v in enumerate(indeg) if v == 0]
while q:
    i = q.pop(0)  # O(n) operation - shifts all remaining elements

Efficient Implementation:

# EFFICIENT: Using deque for O(1) operations
from collections import deque
q = deque(i for i, v in enumerate(indeg) if v == 0)
while q:
    i = q.popleft()  # O(1) operation

These pitfalls can cause incorrect results, runtime errors, or inefficient performance. Always validate index conversions, ensure proper level-wise processing for BFS, and use appropriate data structures for optimal performance.