Course Schedule 1 - Is it Possible
MediumUpdated: Feb 7, 2026
Practice on:
Problem
There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.
- For example, the pair
[0, 1], indicates that to take course0you have to first take course1.
Return true if you can finish all courses. Otherwise, return false.
Examples
Example 1:
Input:
numCourses = 2, prerequisites =[[1,0]]
Output:
true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
Example 2:
Input:
numCourses = 2, prerequisites =[[1,0],[0,1]]
Output:
false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
Solution
This problem can be converted to finding if a graph contains a cycle.
Video explanation
Here is the video explaining this method in detail. Please check it out:
<div class="youtube-embed"><iframe src="https://www.youtube.com/embed/9V5EGPhM51w" frameborder="0" allowfullscreen></iframe></div>
Method 1 - BFS
This solution uses breath-first search and it is easy to understand.
Code
C++
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
if (numCourses == 0 || prerequisites.empty()) {
return true;
}
// counter for number of prerequisites
vector<int> pCounter(numCourses, 0);
for (const auto& prereq : prerequisites) {
pCounter[prereq[0]]++;
}
// store courses that have no prerequisites
queue<int> q;
for (int i = 0; i < numCourses; i++) {
if (pCounter[i] == 0) {
q.push(i);
}
}
// number of courses that have no prerequisites
int numNoPre = q.size();
while (!q.empty()) {
int top = q.front();
q.pop();
for (const auto& prereq : prerequisites) {
// if a course's prerequisite can be satisfied by a course in queue
if (prereq[1] == top) {
pCounter[prereq[0]]--;
if (pCounter[prereq[0]] == 0) {
numNoPre++;
q.push(prereq[0]);
}
}
}
}
return numNoPre == numCourses;
}
};
Go
func canFinish(numCourses int, prerequisites [][]int) bool {
if numCourses == 0 || len(prerequisites) == 0 {
return true
}
// counter for number of prerequisites
pCounter := make([]int, numCourses)
for _, prereq := range prerequisites {
pCounter[prereq[0]]++
}
// store courses that have no prerequisites
queue := []int{}
for i := 0; i < numCourses; i++ {
if pCounter[i] == 0 {
queue = append(queue, i)
}
}
// number of courses that have no prerequisites
numNoPre := len(queue)
for len(queue) > 0 {
top := queue[0]
queue = queue[1:]
for _, prereq := range prerequisites {
// if a course's prerequisite can be satisfied by a course in queue
if prereq[1] == top {
pCounter[prereq[0]]--
if pCounter[prereq[0]] == 0 {
numNoPre++
queue = append(queue, prereq[0])
}
}
}
}
return numNoPre == numCourses
}
Java
public boolean canFinish(int numCourses, int[][] prerequisites) {
if (prerequisites == null) {
throw new IllegalArgumentException("illegal prerequisites array");
}
int len = prerequisites.length;
if (numCourses == 0 || len == 0) {
return true;
}
// counter for number of prerequisites
int[] pCounter = new int[numCourses];
for (int i = 0; i<len; i++) {
pCounter[prerequisites[i][0]]++;
}
//store courses that have no prerequisites
LinkedList<Integer> queue = new LinkedList<Integer> ();
for (int i = 0; i<numCourses; i++) {
if (pCounter[i] == 0) {
queue.add(i);
}
}
// number of courses that have no prerequisites
int numNoPre = queue.size();
while (!queue.isEmpty()) {
int top = queue.remove();
for (int i = 0; i<len; i++) {
// if a course's prerequisite can be satisfied by a course in queue
if (prerequisites[i][1] == top) {
pCounter[prerequisites[i][0]]--;
if (pCounter[prerequisites[i][0]] == 0) {
numNoPre++;
queue.add(prerequisites[i][0]);
}
}
}
}
return numNoPre == numCourses;
}
Kotlin
class Solution {
fun canFinish(numCourses: Int, prerequisites: Array<IntArray>): Boolean {
if (numCourses == 0 || prerequisites.isEmpty()) {
return true
}
// counter for number of prerequisites
val pCounter = IntArray(numCourses)
for (prereq in prerequisites) {
pCounter[prereq[0]]++
}
// store courses that have no prerequisites
val queue = ArrayDeque<Int>()
for (i in 0 until numCourses) {
if (pCounter[i] == 0) {
queue.add(i)
}
}
// number of courses that have no prerequisites
var numNoPre = queue.size
while (queue.isNotEmpty()) {
val top = queue.removeFirst()
for (prereq in prerequisites) {
// if a course's prerequisite can be satisfied by a course in queue
if (prereq[1] == top) {
pCounter[prereq[0]]--
if (pCounter[prereq[0]] == 0) {
numNoPre++
queue.add(prereq[0])
}
}
}
}
return numNoPre == numCourses
}
}
Python
from collections import deque
from typing import List
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
if numCourses == 0 or not prerequisites:
return True
# counter for number of prerequisites
pCounter = [0] * numCourses
for prereq in prerequisites:
pCounter[prereq[0]] += 1
# store courses that have no prerequisites
queue = deque()
for i in range(numCourses):
if pCounter[i] == 0:
queue.append(i)
# number of courses that have no prerequisites
numNoPre = len(queue)
while queue:
top = queue.popleft()
for prereq in prerequisites:
# if a course's prerequisite can be satisfied by a course in queue
if prereq[1] == top:
pCounter[prereq[0]] -= 1
if pCounter[prereq[0]] == 0:
numNoPre += 1
queue.append(prereq[0])
return numNoPre == numCourses
Rust
use std::collections::VecDeque;
impl Solution {
pub fn can_finish(num_courses: i32, prerequisites: Vec<Vec<i32>>) -> bool {
let num_courses = num_courses as usize;
if num_courses == 0 || prerequisites.is_empty() {
return true;
}
// counter for number of prerequisites
let mut p_counter = vec![0; num_courses];
for prereq in &prerequisites {
p_counter[prereq[0] as usize] += 1;
}
// store courses that have no prerequisites
let mut queue = VecDeque::new();
for i in 0..num_courses {
if p_counter[i] == 0 {
queue.push_back(i);
}
}
// number of courses that have no prerequisites
let mut num_no_pre = queue.len();
while let Some(top) = queue.pop_front() {
for prereq in &prerequisites {
// if a course's prerequisite can be satisfied by a course in queue
if prereq[1] as usize == top {
p_counter[prereq[0] as usize] -= 1;
if p_counter[prereq[0] as usize] == 0 {
num_no_pre += 1;
queue.push_back(prereq[0] as usize);
}
}
}
}
num_no_pre == num_courses
}
}
Typescript
function canFinish(numCourses: number, prerequisites: number[][]): boolean {
if (numCourses === 0 || prerequisites.length === 0) {
return true;
}
// counter for number of prerequisites
const pCounter: number[] = new Array(numCourses).fill(0);
for (const [course, prereq] of prerequisites) {
pCounter[course]++;
}
// store courses that have no prerequisites
const queue: number[] = [];
for (let i = 0; i < numCourses; i++) {
if (pCounter[i] === 0) {
queue.push(i);
}
}
// number of courses that have no prerequisites
let numNoPre = queue.length;
while (queue.length > 0) {
const top = queue.shift()!;
for (const [course, prereq] of prerequisites) {
// if a course's prerequisite can be satisfied by a course in queue
if (prereq === top) {
pCounter[course]--;
if (pCounter[course] === 0) {
numNoPre++;
queue.push(course);
}
}
}
}
return numNoPre === numCourses;
}
Complexity
- ⏰ Time complexity:
O(V + E)– whereVis the number of courses andEis the number of prerequisites. We process each course and check all prerequisite relationships. - 🧺 Space complexity:
O(V)– for thepCounterarray and the queue, both of which can store up toVcourses.
Method 2 - DFS
Thsi problem is very close to Topological Sorting.
Code
C++
class Solution {
private:
vector<int> visitState;
unordered_map<int, vector<int>> adj;
bool dfs(int course) {
visitState[course] = 1; // Mark as visiting
// Explore neighbors (prerequisites of 'course')
for (int neighbor : adj[course]) {
if (visitState[neighbor] == 1) {
return false; // Cycle detected: neighbor is currently in DFS path
}
if (visitState[neighbor] == 0) { // If unvisited, recurse
if (!dfs(neighbor)) {
return false; // Propagate cycle detection
}
}
}
visitState[course] = 2; // Mark as visited (fully processed)
return true; // No cycle found in this path
}
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
visitState.resize(numCourses, 0); // All initialized to 0 (unvisited)
// Build adjacency list
for (int i = 0; i < numCourses; i++) {
adj[i] = vector<int>();
}
for (const auto& prereq : prerequisites) {
// prereq[0] -> prereq[1]
// To take prereq[0], you must take prereq[1] first.
// So, add an edge from prereq[0] to prereq[1].
adj[prereq[0]].push_back(prereq[1]);
}
// Perform DFS for each course to detect cycles
for (int i = 0; i < numCourses; i++) {
if (visitState[i] == 0) { // If unvisited, start DFS from this course
if (!dfs(i)) {
return false; // Cycle detected
}
}
}
return true; // No cycles found
}
};
Go
func canFinish(numCourses int, prerequisites [][]int) bool {
visitState := make([]int, numCourses) // All initialized to 0 (unvisited)
adj := make(map[int][]int)
// Build adjacency list
for i := 0; i < numCourses; i++ {
adj[i] = []int{}
}
for _, prereq := range prerequisites {
// prereq[0] -> prereq[1]
// To take prereq[0], you must take prereq[1] first.
// So, add an edge from prereq[0] to prereq[1].
adj[prereq[0]] = append(adj[prereq[0]], prereq[1])
}
var dfs func(int) bool
dfs = func(course int) bool {
visitState[course] = 1 // Mark as visiting
// Explore neighbors (prerequisites of 'course')
for _, neighbor := range adj[course] {
if visitState[neighbor] == 1 {
return false // Cycle detected: neighbor is currently in DFS path
}
if visitState[neighbor] == 0 { // If unvisited, recurse
if !dfs(neighbor) {
return false // Propagate cycle detection
}
}
}
visitState[course] = 2 // Mark as visited (fully processed)
return true // No cycle found in this path
}
// Perform DFS for each course to detect cycles
for i := 0; i < numCourses; i++ {
if visitState[i] == 0 { // If unvisited, start DFS from this course
if !dfs(i) {
return false // Cycle detected
}
}
}
return true // No cycles found
}
Java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
class Solution {
// 0: unvisited, 1: visiting (in current DFS path), 2: visited (fully processed)
private int[] visitState;
private Map<Integer, List<Integer>> adj;
public boolean canFinish(int numCourses, int[][] prerequisites) {
visitState = new int[numCourses]; // All initialized to 0 (unvisited)
adj = new HashMap<>();
// Build adjacency list
for (int i = 0; i < numCourses; i++) {
adj.put(i, new ArrayList<>());
}
for (int[] prereq : prerequisites) {
// prereq[0] -> prereq[1]
// To take prereq[0], you must take prereq[1] first.
// So, add an edge from prereq[0] to prereq[1].
adj.get(prereq[0]).add(prereq[1]);
}
// Perform DFS for each course to detect cycles
for (int i = 0; i < numCourses; i++) {
if (visitState[i] == 0) { // If unvisited, start DFS from this course
if (!dfs(i)) {
return false; // Cycle detected
}
}
}
return true; // No cycles found
}
private boolean dfs(int course) {
visitState[course] = 1; // Mark as visiting
// Explore neighbors (prerequisites of 'course')
for (int neighbor : adj.get(course)) {
if (visitState[neighbor] == 1) {
return false; // Cycle detected: neighbor is currently in DFS path
}
if (visitState[neighbor] == 0) { // If unvisited, recurse
if (!dfs(neighbor)) {
return false; // Propagate cycle detection
}
}
}
visitState[course] = 2; // Mark as visited (fully processed)
return true; // No cycle found in this path
}
}
Kotlin
class Solution {
private lateinit var visitState: IntArray
private lateinit var adj: MutableMap<Int, MutableList<Int>>
fun canFinish(numCourses: Int, prerequisites: Array<IntArray>): Boolean {
visitState = IntArray(numCourses) // All initialized to 0 (unvisited)
adj = mutableMapOf()
// Build adjacency list
for (i in 0 until numCourses) {
adj[i] = mutableListOf()
}
for (prereq in prerequisites) {
// prereq[0] -> prereq[1]
// To take prereq[0], you must take prereq[1] first.
// So, add an edge from prereq[0] to prereq[1].
adj[prereq[0]]!!.add(prereq[1])
}
// Perform DFS for each course to detect cycles
for (i in 0 until numCourses) {
if (visitState[i] == 0) { // If unvisited, start DFS from this course
if (!dfs(i)) {
return false // Cycle detected
}
}
}
return true // No cycles found
}
private fun dfs(course: Int): Boolean {
visitState[course] = 1 // Mark as visiting
// Explore neighbors (prerequisites of 'course')
for (neighbor in adj[course]!!) {
if (visitState[neighbor] == 1) {
return false // Cycle detected: neighbor is currently in DFS path
}
if (visitState[neighbor] == 0) { // If unvisited, recurse
if (!dfs(neighbor)) {
return false // Propagate cycle detection
}
}
}
visitState[course] = 2 // Mark as visited (fully processed)
return true // No cycle found in this path
}
}
Python
from collections import defaultdict
from typing import List
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
# 0: unvisited, 1: visiting (in current DFS path), 2: visited (fully processed)
visit_state = [0] * numCourses
adj = defaultdict(list)
# Build adjacency list
for course, prereq in prerequisites:
# course -> prereq
# To take 'course', you must take 'prereq' first.
# So, add an edge from 'course' to 'prereq'.
adj[course].append(prereq)
# Perform DFS for each course to detect cycles
for i in range(numCourses):
if visit_state[i] == 0: # If unvisited, start DFS from this course
if not self._dfs(i, visit_state, adj):
return False # Cycle detected
return True # No cycles found
def _dfs(self, course: int, visit_state: List[int], adj: defaultdict[list]) -> bool:
visit_state[course] = 1 # Mark as visiting
# Explore neighbors (prerequisites of 'course')
for neighbor in adj[course]:
if visit_state[neighbor] == 1:
return False # Cycle detected: neighbor is currently in DFS path
if visit_state[neighbor] == 0: # If unvisited, recurse
if not self._dfs(neighbor, visit_state, adj):
return False # Propagate cycle detection
visit_state[course] = 2 # Mark as visited (fully processed)
return True # No cycle found in this path
Rust
use std::collections::HashMap;
impl Solution {
pub fn can_finish(num_courses: i32, prerequisites: Vec<Vec<i32>>) -> bool {
let num_courses = num_courses as usize;
let mut visit_state = vec![0; num_courses]; // All initialized to 0 (unvisited)
let mut adj: HashMap<usize, Vec<usize>> = HashMap::new();
// Build adjacency list
for i in 0..num_courses {
adj.insert(i, Vec::new());
}
for prereq in &prerequisites {
// prereq[0] -> prereq[1]
// To take prereq[0], you must take prereq[1] first.
// So, add an edge from prereq[0] to prereq[1].
adj.get_mut(&(prereq[0] as usize)).unwrap().push(prereq[1] as usize);
}
fn dfs(
course: usize,
visit_state: &mut Vec<i32>,
adj: &HashMap<usize, Vec<usize>>,
) -> bool {
visit_state[course] = 1; // Mark as visiting
// Explore neighbors (prerequisites of 'course')
for &neighbor in &adj[&course] {
if visit_state[neighbor] == 1 {
return false; // Cycle detected: neighbor is currently in DFS path
}
if visit_state[neighbor] == 0 { // If unvisited, recurse
if !dfs(neighbor, visit_state, adj) {
return false; // Propagate cycle detection
}
}
}
visit_state[course] = 2; // Mark as visited (fully processed)
true // No cycle found in this path
}
// Perform DFS for each course to detect cycles
for i in 0..num_courses {
if visit_state[i] == 0 { // If unvisited, start DFS from this course
if !dfs(i, &mut visit_state, &adj) {
return false; // Cycle detected
}
}
}
true // No cycles found
}
}
Typescript
function canFinish(numCourses: number, prerequisites: number[][]): boolean {
const visitState: number[] = new Array(numCourses).fill(0); // All initialized to 0 (unvisited)
const adj: Map<number, number[]> = new Map();
// Build adjacency list
for (let i = 0; i < numCourses; i++) {
adj.set(i, []);
}
for (const [course, prereq] of prerequisites) {
// course -> prereq
// To take course, you must take prereq first.
// So, add an edge from course to prereq.
adj.get(course)!.push(prereq);
}
function dfs(course: number): boolean {
visitState[course] = 1; // Mark as visiting
// Explore neighbors (prerequisites of 'course')
for (const neighbor of adj.get(course)!) {
if (visitState[neighbor] === 1) {
return false; // Cycle detected: neighbor is currently in DFS path
}
if (visitState[neighbor] === 0) { // If unvisited, recurse
if (!dfs(neighbor)) {
return false; // Propagate cycle detection
}
}
}
visitState[course] = 2; // Mark as visited (fully processed)
return true; // No cycle found in this path
}
// Perform DFS for each course to detect cycles
for (let i = 0; i < numCourses; i++) {
if (visitState[i] === 0) { // If unvisited, start DFS from this course
if (!dfs(i)) {
return false; // Cycle detected
}
}
}
return true; // No cycles found
}
Complexity
- ⏰ Time complexity:
O(V + E)– whereVis the number of courses andEis the number of prerequisites. Each course is visited once, and each edge (prerequisite relationship) is traversed once during DFS. - 🧺 Space complexity:
O(V + E)– for the adjacency list which stores all edges, plusO(V)for the recursion stack and visit state array, resulting inO(V + E)total space.