Parallel Courses
Plan a degree. Courses are numbered 1 to n, and a pair [a, b] in relations means course a must be finished before course b can start. A semester holds as many courses as you like, provided every prerequisite of each one was finished in an earlier semester (not in the same one). Return the fewest semesters that finish every course, or -1 if the prerequisites make that impossible. Limits: 1 <= n <= 100000, 0 <= relations.length <= 200000, 1 <= a, b <= n and a != b. The same pair may be listed more than once. The answer is -1 or a number from 1 to n. Think about: a chain of prerequisites can run thousands of courses deep, so mind your stack if you recurse. Example: n = 7, relations = [[1,3],[2,3],[3,5],[4,5],[5,7],[6,7]] => 4 semester 1: courses 1, 2, 4, 6 (nothing to wait for) semester 2: course 3 (needs 1 and 2) semester 3: course 5 (needs 3 and 4) semester 4: course 7 (needs 5 and 6)
You're planning a degree where some courses have to be finished before others, and a semester can hold as many courses as you like once their prerequisites are behind you. How few semesters get you through everything, or is the plan impossible? Interviewers love it because it's a dependency graph in disguise, and the classic trap is a loop of prerequisites that quietly breaks the answer. Expect up to 100,000 courses and 200,000 prerequisite pairs.
Examples
You write
minimum_semesters(n: int, relations: List[List[int]])
Example 1
- Input
- n = 7, relations = [[1,3],[2,3],[3,5],[4,5],[5,7],[6,7]]
- returns
- 4
Example 2
- Input
- n = 1, relations = []
- returns
- 1
Save this for your laptop
The editor and Run need a bigger screen. The link opens Parallel Courses ready to code. It is free, and the editor needs no account.
The pattern behind it
Graphs
I reach for it when
- The input is edges, prerequisites or connections.
- You need cycles, an ordering or connected groups.
Say this before you type. Say whether the edges are directed, and which of the three jobs you are doing.
All 32 Graphs problemsDynamic Programming
I reach for it when
- Brute force repeats the same subproblem.
- You are asked for a count, a minimum or a maximum.
Say this before you type. Say the state in one sentence, then say which smaller states it reads from.
All 37 Dynamic Programming problems
Meet Coco
Coco is an AI study partner, not a person. She listens while you explain your code, asks what a line does and never hands you the fix. Sign in free to type with Coco, up to a daily limit, and to talk with her for one hour. After that, talking comes with the $79 pack. Anyone can open the editor and run their code.