Is Parallel Courses easy or hard?

Parallel Courses is generally considered a medium-level graph problem. The main challenge is recognizing that the course dependency structure forms a directed graph and that topological sorting can determine a valid processing order and detect cycles.

Parallel Courses Python/Java solution

Most implementations follow the same structure across languages: build the adjacency list, compute in-degrees, push zero in-degree nodes into a queue, and run BFS. Python commonly uses collections.deque, while Java implementations use Queue and ArrayList for adjacency storage.

How to solve Parallel Courses in O(V+E)?

Construct a directed graph from prerequisite relations and compute the in-degree of every course. Push all nodes with in-degree 0 into a queue and perform BFS. For each processed course, decrement the in-degree of its neighbors and add newly unlocked courses to the queue. Counting BFS levels gives the minimum number of semesters.

What is the best approach for Parallel Courses?

Topological sorting using Kahn's algorithm (BFS) is the most practical approach. Build an adjacency list and track in-degrees for each course, then process nodes with zero prerequisites level by level. Each BFS layer represents one semester. The algorithm runs in O(V+E) time and naturally detects cycles.

Is Parallel Courses asked at Google/Amazon/Meta?

Graph scheduling problems using topological sort frequently appear in interviews at companies like Google, Amazon, and Meta. Variants include course scheduling, dependency resolution, and build order problems. Parallel Courses specifically tests understanding of DAG traversal and BFS-based topological sorting.

What data structure is used in Parallel Courses?

The solution typically uses an adjacency list to represent the directed graph, an array to track in-degrees, and a queue for BFS processing. These structures allow efficient updates when prerequisites are satisfied and enable level-by-level traversal for semester counting.

What is the time complexity of Parallel Courses?

The optimal solution runs in O(V+E) time where V is the number of courses and E is the number of prerequisite relations. Building the graph takes O(E) and the topological traversal processes each node and edge once. Space complexity is also O(V+E) for the adjacency list and in-degree array.

Description Hints 3 Solution Video 13:52

1136. Parallel Courses

Medium62.1% acceptance7 companiesPremium elsewhere, free here

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

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

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 <= prevCourse_i, nextCourse_i <= n
prevCourse_i != nextCourse_i
All the pairs [prevCourse_i, nextCourse_i] are unique.

Asked at 7 companies

Netflix Snowflake Uber

Google Tiktok Amazon Meta

Topics

Graph Topological Sort

Hints open one at a time

Hint 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.

Hint 2

The graph is a directed acyclic graph (DAG). The answer is the longes path in this DAG.

Hint 3

You can use DP to find the longest path in the DAG.

13:52

Still stuck?Read the written solution, or watch a walkthrough.

Open solution