Course Schedule

Medium · Graphs

You are given the total number of courses, numbered from 0, and a list of prerequisite pairs where [a, b] means you must finish course b before course a. Determine whether it is possible to complete all courses given these requirements. Return true if there is some valid order to take all courses, or false if the prerequisites form a cycle that makes it impossible.

Examples

Input:  numCourses = 2, prerequisites = [[1,0]]
Output: true
Why:    Take course 0 first, then course 1; no cycle exists.

Input:  numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Why:    Course 0 needs course 1 and course 1 needs course 0, an impossible cycle.

Input:  numCourses = 4, prerequisites = [[1,0],[2,1],[3,2]]
Output: true
Why:    The chain 0 -> 1 -> 2 -> 3 has no cycle so all courses can be finished in that order.

Constraints

1 <= numCourses <= 2000, 0 <= prerequisites.length <= 5000, prerequisites[i].length == 2, 0 <= a, b < numCourses

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Course Schedule

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Course Schedule. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.