336. Valid Course Order with Prerequisites

Valid Course Order with Prerequisites

There are numCourses courses labeled from 0 to numCourses - 1. Some courses must be completed before other courses can be taken.

Each prerequisite is represented by a string "course,prerequisite". It means that prerequisite must be completed before course.

Return an order in which all courses can be completed. If no such order exists because the prerequisite relationships contain a cycle, return an empty list.

Class Definition

CourseScheduler()

Method Signature

List<Integer> findOrder(int numCourses, List<String> prerequisites)

numCourses is the total number of courses.
prerequisites contains strings in the format "course,prerequisite".
Returns a list containing every course in a valid completion order.
Returns an empty list when completing all courses is impossible.

Ordering Rule

When multiple courses are available to take at the same time, choose the course with the smaller number first. Therefore, the returned order is deterministic.

Constraints

1 ≤ numCourses ≤ 2,000
0 ≤ prerequisites.size() ≤ numCourses * (numCourses - 1)
Every prerequisite string contains exactly two comma-separated integers.
0 ≤ course < numCourses
0 ≤ prerequisite < numCourses
course != prerequisite
Every prerequisite relationship is unique.

Examples

Example 1

findOrder(numCourses = 6, prerequisites = List.of("2,0", "2,1", "3,1", "4,2", "4,3", "5,4"))

Output: [0, 1, 2, 3, 4, 5]

Courses 0 and 1 are initially available, so course 0 is selected first. After all prerequisites are satisfied, every course can be completed in the displayed order.

Example 2

findOrder(numCourses = 4, prerequisites = List.of("1,0", "2,1", "0,2"))

Output: []

Courses 0, 1, and 2 form a cycle, so it is impossible to complete every course.

Example 3

findOrder(numCourses = 5, prerequisites = List.of())

Output: [0, 1, 2, 3, 4]

There are no prerequisite relationships, so courses are returned in increasing numerical order.

Example 4

findOrder(numCourses = 5, prerequisites = List.of("3,0", "3,2", "4,1"))

Output: [0, 1, 2, 3, 4]

Courses 0, 1, and 2 are initially available. Selecting the smallest available course each time produces the displayed valid order.