Course ScheduleMedium

Course Schedule

Medium 16.2k47% acceptance

GraphDepth-First SearchBreadth-First SearchTopological Sort

There are numCourses courses labeled 0 to numCourses - 1. You are given a list prerequisites where each entry [course, prereq] means you must finish prereq before course.

Return true if it is possible to finish every course, otherwise false.

This is possible exactly when the prerequisite graph has no cycle.

Example 1

Input: numCourses = 2, prerequisites = [[1,0]]

Output: true

Take course 0, then course 1. No cycle, so all courses are reachable.

Example 2

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]

Output: false

0 needs 1 and 1 needs 0 — a cycle, so neither can be started.

Example 3

Input: numCourses = 3, prerequisites = []

Output: true

Constraints

1 ≤ numCourses ≤ 2000
0 ≤ prerequisites.length ≤ 5000
Each prerequisite pair is distinct; 0 ≤ course, prereq < numCourses.

Asked atAmazonGoogleMetaMicrosoftApple

JavaScript

⌘↵ to run

Loading editor…

Case 1

2, [[1,0]]

expected: true

Case 2

2, [[1,0],[0,1]]

expected: false

Case 3

3, []

expected: true

Case 4

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

expected: true

Case 5

3, [[0,1],[1,2],[2,0]]

expected: false

Case 6

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

expected: true

Case 7

1, []

expected: true