Practice/Netflix/Parallel Courses

Parallel Courses

CodingMust

Problem Overview

You are given an integer n representing courses labeled from 1 to n, and an array relations where relations[i] = [prevCourse, nextCourse] indicates that prevCourse must be taken before nextCourse.

In one semester, you can take any number of courses as long as you have completed all prerequisites in previous semesters.

Return the minimum number of semesters needed to complete all courses. If there is a circular dependency (making it impossible to complete all courses), return -1.

This is a classic topological sort problem that can be solved using Kahn's algorithm (BFS-based) or DFS-based cycle detection.

Example 1

` n = 3 relations = [[1,3],[2,3]]

Output: 2

Explanation:

Semester 1: Take courses 1 and 2 (no prerequisites)

Semester 2: Take course 3 (prerequisites 1 and 2 completed)

`

Example 2

` n = 3 relations = [[1,2],[2,3],[3,1]]

Output: -1

Explanation:

Course 1 requires 3, which requires 2, which requires 1

This is a circular dependency - impossible to complete

`

Requirements

• Detect cycles in the course dependency graph
• Find the longest path in the DAG (directed acyclic graph) if no cycles exist
• Handle up to 5000 courses and 5000 prerequisite relationships efficiently
• Courses are labeled from 1 to n, not 0 to n-1

Clarification Questions to Ask

• Can we assume all course numbers in relations are valid (between 1 and n)?
• Should we handle edge cases like n = 1 with no relations?
• Is there a preferred approach (BFS vs DFS)?