1136. Parallel Courses

Parallel Courses (LeetCode 1136) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Graph BFS - Topological Sort (Kahn's Algorithm) subpattern.

How to solve Parallel Courses

Parallel Courses is a Topological Sort problem, part of Graph Traversal Patterns (DFS & BFS). Master topological sorting using Kahn's BFS algorithm. Solve course schedule and build order problems.

Work towards the solution in these steps:

1. Try to think of it as a graph problem. It will be impossible to study all the courses if the graph had a cycle.
2. The graph is a directed acyclic graph (DAG). The answer is the longes path in this DAG.
3. You can use DP to find the longest path in the DAG.

The reference solution runs in O(|V| + |E|) time and O(|E|) space.

The Parallel Courses solution and editorial walks through the full approach with reference code.

Problem statement

You are given an integer n representing the number of courses labeled from 1 to n. You are also given a 2D integer array relations where relations[i] = [prevCoursei, nextCoursei] denotes that course prevCoursei must 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 courses you are taking in previous semesters.

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

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 they are prerequisites of each other.

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.

Topics and companies

Topics: Graph, Topological Sort.

Reported in interviews at Google, Uber.

How to practise Parallel Courses on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(|V| + |E|) time and O(|E|) space.

Open Parallel Courses in the code editor, or read the Parallel Courses editorial for a worked solution with its approach and complexity analysis.

Where Parallel Courses sits in the DSA pattern sheet

• Graph Traversal Patterns (DFS & BFS) pattern guide
• Graph BFS - Topological Sort (Kahn's Algorithm) subpattern
• The full DSA patterns sheet

Problems related to Parallel Courses

Other problems that use the same Graph BFS - Topological Sort (Kahn's Algorithm) and Graph Traversal Patterns (DFS & BFS) techniques:

• Alien Dictionary — Hard, same subpattern
• Build a Matrix With Conditions — Hard, same subpattern
• Course Schedule IV — Medium, same subpattern
• Find All Possible Recipes from Given Supplies — Medium, same subpattern
• Largest Color Value in a Directed Graph — Hard, same subpattern
• Minimum Height Trees — Medium, same subpattern

Parallel Courses FAQ