Tue 21 Dec 2021

Course Schedule Leetcode Solution

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] = [a_i, b_i] indicates that you must take course b_i first if you want to take course a_i.

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Testcase

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.

Constraints:

1 <= numCourses <= 105
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
All the pairs prereq

Explanation

Lets take a good test case like

numCourses = 5
prerequisites = [[1,4],[2,4],[3,1],[3,2]]

Here

4 is prerequisite for both 1 and 2
1 is a prerequisite for 3
2 is a prerequisite for 3.

We can visuallize it as a directed graph.

This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.

Solution

Java
Python

	class Solution {

	Map<Integer, List> adj = new HashMap<>();

	public List<Integer> getNeighbour(int n){
	return new ArrayList<>(adj.get(n));
	}

	public boolean canFinish(int numCourses, int[][] prerequisites) {

	if (prerequisites.length == 0){
	return true;
	}

	int[] indegree = new int[numCourses];

	for (int i = 0; i < prerequisites.length; i++){
	adj.computeIfAbsent(prerequisites[i][1],
	k -> new ArrayList<>()).add(prerequisites[i][0]);
	indegree[prerequisites[i][0]]++;

	}

	Deque<Integer> queue = new ArrayDeque<>();

	for (int i = 0; i < indegree.length; i++){
	if (indegree[i] == 0){
	queue.offer(i);
	}
	}

	int count = 0;

	while (!queue.isEmpty()) {
	int current = queue.poll();

	if (indegree[current] == 0 ){
	count++;
	}

	if (!adj.containsKey(current)) {
	continue;
	}

	for (int neighbour : getNeighbour(current)){
	indegree[neighbour]--;
	if (indegree[neighbour] == 0 ){
	queue.offer(neighbour);
	}
	}
	}

	return numCourses == count;
	}
	}

view raw CourseSchedule.java hosted with ❤ by GitHub

	from collections import deque

	class Solution:

	def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:

	if len(prerequisites) == 0:
	return True

	graph = [[] for _ in range(numCourses)]

	indegree = [0] * numCourses

	for a, b in prerequisites:
	graph[b].append(a)
	indegree[a] += 1


	queue = deque()

	for i in range(0, len(indegree)):
	if indegree[i] == 0:
	queue.append(i)

	count = 0

	while len(queue) > 0:
	current = queue.popleft()

	if indegree[current] == 0:
	count += 1

	if not graph[current]:
	print(f'{current} doesnt exit in {graph}')
	continue

	for neighbour in graph[current]:
	indegree[neighbour] -= 1
	if indegree[neighbour] == 0:
	queue.append(neighbour)


	return True if count == numCourses else False

view raw course_schedule.py hosted with ❤ by GitHub

Complexity

Time complexity: $∣ V ∣ + ∣ E ∣$ .

V : numCourses & E : prerequisites

Footnotes

207. Course Schedule
↩