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

For each course, recurse into its prerequisites and keep the latest finish; no memory with time complexity O(N · 2^N) and space complexity O(N).

What is the optimal approach and complexity for Parallel Courses III?

Process courses in prerequisite order; each course keeps the latest finish of its prerequisites with optimal time complexity O(N + R) and space complexity O(N + R).

How do you identify the pattern for Parallel Courses III?

Look for key signals in the prompt: "minimum months to complete all courses" indicates A total time along the way, not a count of layers.; "courses can run at the same time" indicates Two courses with no path between them overlap, so only the longest chain matters.; "start as soon as prerequisites are finished" indicates Each course starts at the largest finish month of its prerequisites..

Parallel Courses III

Hard·LeetCode #2050 Pro OnlyMedium

LeetCode

Problem Statement

There are n courses, labelled 1 to n. Course i takes time[i − 1] months. Each pair relations[j] = [prevCourse, nextCourse] means prevCourse must be finished before nextCourse can start.

Any number of courses can run at the same time. A course starts the moment all its prerequisites are finished. Return the minimum number of months needed to finish every course.

Input

n, the number of courses, relations, a list of pairs [prevCourse, nextCourse], and time, where time[i] is the length of course i + 1.

Output

The earliest month in which every course is finished.

Example 1

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

Output: 8

Courses 1 and 2 start at month 0 and finish at months 3 and 2. Course 3 waits for both, so it starts at month 3 and ends at 3 + 5 = 8.

Example 2

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

Output: 12

Courses 1, 2 and 3 start at month 0. Course 4 waits for 3 and runs until 3 + 4 = 7. Course 5 waits for 1, 2, 3 and 4, so it starts at month 7 and ends at 7 + 5 = 12.

Constraints

• 1 ≤ n ≤ 5 × 10^4
• 0 ≤ relations.length ≤ min(n · (n − 1) / 2, 5 × 10^4)
• relations[j].length == 2
• 1 ≤ prevCourse, nextCourse ≤ n
• prevCourse ≠ nextCourse
• All the pairs [prevCourse, nextCourse] are unique.
• time.length == n
• 1 ≤ time[i] ≤ 10^4
• The graph is a directed acyclic graph.

Pattern Recognition Clues

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

“minimum months to complete all courses”

→ A total time along the way, not a count of layers.

“courses can run at the same time”

→ Two courses with no path between them overlap, so only the longest chain matters.

“start as soon as prerequisites are finished”

→ Each course starts at the largest finish month of its prerequisites.

Approach Complexity Ladder

Brute Force — recursive walk back from every courseO(N · 2^N)O(N)

For each course, recurse into its prerequisites and keep the latest finish; no memory

Optimal — Kahn's queue carrying the latest finishO(N + R)O(N + R)

Process courses in prerequisite order; each course keeps the latest finish of its prerequisites

Brute Force Intuition

A course finishes at (the latest finish of its prerequisites) + its own time. A course with no prerequisites finishes at its own time. Work this out for every course with a plain recursion that remembers nothing. The answer is the largest finish month.

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

Parallel Courses Minimum Height Trees