This is our solution and implementation to problem #1136: Parallel Courses on LeetCode.
Our code is written in Java. If you want to code your solution in a different language, no worries, as the core concepts will carry over from language to language. This page includes our analysis of the problem, our implementation strategy a breakdown on the space and time complexity, and the full code implementation.
If you would like to view the original problem and solve it, please visit: Parallel Courses on LeetCode.
Problem Analysis
You can visualize a series of courses and their prerequisites as a series of acyclic graphs. They might not all be connected. The relationship between nodes is the path you would have to take for all prerequisites of each course. The minimum number of semesters needed is equal to the maximum path along one of these graphs. If there are any cycles, you can't take all of the courses.
Implementation Strategy
We will:
- Convert the courses to a list of list representing nodes on a graph and their connections.
- Create a cache visitedNodeDepths to memoize previous traversals. That way, if we encounter a subgraph we've already traversed, we don't have to traverse it again.
- Find the list of courses that have no prerequisites. This will help us find entry points to the graph.
- For each entry point, find the maximum depth (path size). Record the maximum along the way.
Space and Time Complexity
The time complexity is O(n+r), since we take n and r operations to prepare the graph and another n to visit each node exactly one. The space complexity os O(n+r), since we have a constant amount of objects that take n space and the collection of edges takes r space.
Additional Resources
The links below outline some of the points discussed above in more detail.
Full Code
Our solution is given in the Java code below:
All of our solutions are hosted on GitHub. The code on this page was pulled from the repo.