We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Parallel Courses

Number: 1101

Difficulty: Medium

Paid? Yes

Companies: TikTok, Google, Uber

Problem Description

You are given n courses labeled from 1 to n and a list of prerequisite pairs. Each pair [prevCourse, nextCourse] indicates that course prevCourse must be taken before course nextCourse. In one semester, you can take any number of courses provided you have completed all the prerequisite courses in previous semesters. Return the minimum number of semesters required to complete all courses. If it is impossible to complete all courses (i.e. there is a cycle), return -1.

Key Insights

  • Model the problem as a directed graph where nodes are courses and edges represent prerequisites.
  • Use topological sorting (Kahn’s algorithm) to process courses with zero prerequisites.
  • Each level (or layer) of processing represents one semester.
  • Detect cycles by ensuring all courses are eventually processed; if not, a cycle exists.
  • The number of BFS levels gives the minimum number of semesters necessary.

Space and Time Complexity

Time Complexity: O(n + m) where n is the number of courses and m is the length of relations (prerequisites). Space Complexity: O(n + m) for storing the graph, in-degree counts, and the processing queue.

Solution

We solve the problem using a topological sort with Kahn's algorithm. First, construct a graph representation using an adjacency list and compute the in-degree for each course. Initialize a queue with courses that have no prerequisites (in-degree == 0). Then, process courses level by level. Each level processed represents one semester. For every course taken in that semester, decrease the in-degree of all its neighbors. Add any neighbor with an in-degree that becomes zero to the queue for the next semester. If, after processing, the total courses taken is less than n, then a cycle exists and return -1. Otherwise, the number of semesters processed is the answer.

Code Solutions

# Python Implementation

from collections import deque

def minimumSemesters(numCourses, relations):
    # Build graph and in-degree dictionary.
    graph = {i: [] for i in range(1, numCourses + 1)}
    in_degree = {i: 0 for i in range(1, numCourses + 1)}
    
    # Construct graph from relations.
    for pre, course in relations:
        graph[pre].append(course)
        in_degree[course] += 1

    # Initialize queue with all courses having no prerequisites.
    queue = deque()
    for course in range(1, numCourses + 1):
        if in_degree[course] == 0:
            queue.append(course)
    
    semesters = 0
    takenCourses = 0
    
    # Process each level (semester) using BFS.
    while queue:
        semesters += 1
        current_level_size = len(queue)
        for _ in range(current_level_size):
            course = queue.popleft()
            takenCourses += 1
            # Decrement in-degree for neighboring courses.
            for neighbor in graph[course]:
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)
    
    # If not all courses have been taken, a cycle exists.
    return semesters if takenCourses == numCourses else -1

# Example usage:
print(minimumSemesters(3, [[1, 3], [2, 3]]))  # Expected output: 2
← Back to All Questions