What is the brute force approach and complexity for Parallel Courses?

Each semester, scan every course and take the ready ones; stop when none is ready with time complexity O(N · (N + R)) and space complexity O(N + R).

What is the optimal approach and complexity for Parallel Courses?

Process the ready courses one semester at a time; the number of semesters is the answer with optimal time complexity O(N + R) and space complexity O(N + R).

How do you identify the pattern for Parallel Courses?

Look for key signals in the prompt: "minimum number of semesters" indicates Count rounds of the queue, not courses: the answer is the number of layers.; "any number of courses in a semester" indicates One semester is one layer. Every course that is ready is taken together.; "return -1 if impossible" indicates A cycle: some courses never reach in-degree 0..

Parallel Courses

Medium·LeetCode #1136 Premium Pro OnlySlight Variation

LeetCode

Problem Statement

There are n courses, labelled 1 to n. Each pair relations[i] = [prevCourse, nextCourse] means prevCourse must be taken in an earlier semester than nextCourse.

In one semester you can take any number of courses, as long as every prerequisite of each course was taken in an earlier semester. Return the minimum number of semesters needed to take every course. If it is impossible, return -1.

Input

n, the number of courses, and relations, a list of pairs [prevCourse, nextCourse].

Output

The minimum number of semesters, or -1 when the relations contain a loop.

Example 1

Input: n = 6, relations = [[1, 2], [1, 3], [2, 4], [3, 4], [4, 5], [6, 5]]

Output: 4

Semester 1 takes courses 1 and 6, which need nothing. Semester 2 takes 2 and 3. Semester 3 takes 4. Semester 4 takes 5. Six courses fit in four semesters, because courses that are ready at the same time share a semester.

Example 2

Input: n = 3, relations = [[1, 2], [2, 3], [3, 1]]

Output: -1

Course 2 needs 1, course 3 needs 2 and course 1 needs 3. Nothing can be taken first, so the answer is -1.

Constraints

• Courses are labelled 1 to n.
• Each relation is [prevCourse, nextCourse], with both labels in that range.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“minimum number of semesters”

→ Count rounds of the queue, not courses: the answer is the number of layers.

“any number of courses in a semester”

→ One semester is one layer. Every course that is ready is taken together.

“return -1 if impossible”

→ A cycle: some courses never reach in-degree 0.

Approach Complexity Ladder

Brute Force — simulate semester by semesterO(N · (N + R))O(N + R)

Each semester, scan every course and take the ready ones; stop when none is ready

Optimal — Kahn's queue, one layer per semesterO(N + R)O(N + R)

Process the ready courses one semester at a time; the number of semesters is the answer

Brute Force Intuition

Keep track of the taken courses. Each semester, scan every course that is not taken. A course is ready when all its prerequisites were taken in an earlier semester. Take all the ready courses together, but only after the scan finishes. Count the semesters. If a semester takes nothing while courses are left, return -1.

Recognition rule for this sub-pattern:

Queue all in-degree-0 nodes; removing one lowers its neighbours' in-degree.

Remember this · Topological Sort

Trigger

Prerequisites, dependencies, build order, "can all courses be finished?", ordering letters from sorted words.

Think

Is this a directed graph where some things must happen before others?

Key question

Which nodes currently have in-degree 0?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Topological Sort translate into production architectures and low-level memory mechanics.

LLD Practice

Task Scheduler & Workflow Orchestrator

Resolving DAG build pipelines and asynchronous task dependency resolution.

Explore Track

C++ Internals

Static vs Global Linkage & Init Order Fiasco

Why compilers resolve static global variables as a DAG to prevent runtime crashes.

Explore Track

Course Schedule II Parallel Courses III