Last updated on January 5th, 2025 at 01:20 am

Here, we see Course Schedule LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Breadth-First Search, Depth-First Search, Graph, Topological Sort

Companies

Apple, Uber, Yelp, Zenefits

Level of Question

Medium

Course Schedule LeetCode Solution

1. Problem Statement

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.

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.

2. Coding Pattern Used in Solution

The coding pattern used in the provided code is Topological Sort. This pattern is commonly used to determine the order of tasks (or courses in this case) that must be completed when there are dependencies between them. It is implemented using Kahn’s Algorithm, which uses a queue to process nodes with zero in-degree and iteratively reduces the in-degree of their neighbors.

3. Code Implementation in Different Languages

3.1 Course Schedule C++

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> adj[numCourses];
        vector<int> indegree(numCourses, 0);
        vector<int> ans;
        for(auto x: prerequisites){
            adj[x[0]].push_back(x[1]);
            indegree[x[1]]++;
        }
        queue<int> q;
        for(int i = 0; i < numCourses; i++){
            if(indegree[i] == 0){
                q.push(i);
            }
        }
        while(!q.empty()){
            auto t = q.front();
            ans.push_back(t);
            q.pop();
            for(auto x: adj[t]){
                indegree[x]--;
                if(indegree[x] == 0){
                    q.push(x);
                }
            }
        }
        return ans.size() == numCourses;
    }
};

3.2 Course Schedule Java

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        ArrayList[] graph = new ArrayList[numCourses];
        int[] degree = new int[numCourses];
        Queue queue = new LinkedList();
        int count=0;
        for(int i=0;i<numCourses;i++)
            graph[i] = new ArrayList();
        for(int i=0; i<prerequisites.length;i++){
            degree[prerequisites[i][1]]++;
            graph[prerequisites[i][0]].add(prerequisites[i][1]);
        }
        for(int i=0; i<degree.length;i++){
            if(degree[i] == 0){
                queue.add(i);
                count++;
            }
        }
        while(queue.size() != 0){
            int course = (int)queue.poll();
            for(int i=0; i<graph[course].size();i++){
                int pointer = (int)graph[course].get(i);
                degree[pointer]--;
                if(degree[pointer] == 0){
                    queue.add(pointer);
                    count++;
                }
            }
        }
        if(count == numCourses)
            return true;
        else    
            return false;
    }
}

3.3 Course Schedule JavaScript

var canFinish = function(numCourses, prerequisites) {
    const order = [];
    const queue = [];
    const graph = new Map();
    const indegree = Array(numCourses).fill(0);
    for (const [e, v] of prerequisites) {
        if (graph.has(v)) {
        graph.get(v).push(e);
        } else {
        graph.set(v, [e]);
        }
        indegree[e]++;
    }
    for (let i = 0; i < indegree.length; i++) {
        if (indegree[i] === 0) queue.push(i);
    }
    while (queue.length) {
        const v = queue.shift();
        if (graph.has(v)) {
        for (const e of graph.get(v)) {
            indegree[e]--;
            if (indegree[e] === 0) queue.push(e);
        }
        }
        order.push(v);
    }
    return numCourses === order.length;
};

3.4 Course Schedule Python

class Solution(object):
    def canFinish(self, numCourses, prerequisites):
        adj = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses
        ans = []
        for pair in prerequisites:
            course = pair[0]
            prerequisite = pair[1]
            adj[prerequisite].append(course)
            indegree[course] += 1
        queue = deque()
        for i in range(numCourses):
            if indegree[i] == 0:
                queue.append(i)
        while queue:
            current = queue.popleft()
            ans.append(current)
            for next_course in adj[current]:
                indegree[next_course] -= 1
                if indegree[next_course] == 0:
                    queue.append(next_course)
        return len(ans) == numCourses

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(V + E)	O(V + E)
Java	O(V + E)	O(V + E)
JavaScript	O(V + E)	O(V + E)
Python	O(V + E)	O(V + E)

where,
V is the number of courses (nodes).
E is the number of prerequisites (edges).

The algorithm is efficient for large graphs as it processes each node and edge exactly once.
The space complexity is proportional to the size of the graph representation and the queue used for processing.
The implementation is consistent across all languages, with minor differences in syntax and data structure usage.