207. Course Schedule – Leetcode Solutions

August 15, 2024

Table of Contents

Description

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.

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 in Python

Python

from collections import defaultdict, deque

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        # Step 1: Create an adjacency list to represent the graph
        graph = defaultdict(list)
        # Step 2: Create an array to track the in-degree (number of incoming edges) of each course
        in_degree = [0] * numCourses
        
        # Step 3: Fill the graph and the in-degree array
        for course, prereq in prerequisites:
            graph[prereq].append(course)
            in_degree[course] += 1
        
        # Step 4: Initialize a queue with courses that have no prerequisites (in-degree of 0)
        queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
        
        # Step 5: Track the number of courses that have been processed
        processed_courses = 0
        
        while queue:
            # Remove a course from the front of the queue
            current_course = queue.popleft()
            processed_courses += 1  # Increment the count of processed courses
            
            # For each course dependent on the current course
            for neighbor in graph[current_course]:
                # Decrease the in-degree (prerequisite count) of the dependent course
                in_degree[neighbor] -= 1
                
                # If in-degree of the dependent course is 0, add it to the queue
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)
        
        # Step 6: If all courses have been processed, return True, else return False
        return processed_courses == numCourses

Explanation:

Graph Representation:
- We represent the courses and their prerequisites using an adjacency list (graph).
- graph[prereq].append(course) means that to take course, you must first take prereq.
In-Degree Array:
- We use the in_degree array to keep track of how many prerequisites each course has.
- in_degree[course] += 1 increases the count for each course that has a prerequisite.
Queue Initialization:
- We initialize a queue with all courses that have no prerequisites (i.e., in_degree[i] == 0).
- These courses can be taken immediately.
Processing Courses:
- We process each course by removing it from the queue and reducing the in-degree of its dependent courses.
- If a dependent course’s in-degree becomes 0, it means all its prerequisites have been satisfied, so it is added to the queue.
Cycle Detection:
- If we can process all the courses (processed_courses == numCourses), it means there’s no cycle in the graph, and we can complete all courses.
- If not, there is a cycle, making it impossible to complete all the courses.

Time Complexity:

The time complexity is O(V + E), where V is the number of courses (numCourses) and E is the number of dependencies (prerequisites.length).

Space Complexity:

The space complexity is O(V + E) due to the graph and in-degree array.

This solution efficiently determines whether it is possible to finish all courses given the prerequisites.

Solution in Javascript

JavaScript

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
var canFinish = function(numCourses, prerequisites) {
    // Step 1: Create an adjacency list to represent the graph
    const graph = new Map();
    // Step 2: Create an array to track the in-degree (number of incoming edges) of each course
    const inDegree = new Array(numCourses).fill(0);
    
    // Step 3: Initialize the graph and in-degree array
    for (let [course, prereq] of prerequisites) {
        if (!graph.has(prereq)) {
            graph.set(prereq, []);
        }
        graph.get(prereq).push(course);
        inDegree[course] += 1;
    }
    
    // Step 4: Initialize a queue with courses that have no prerequisites (in-degree of 0)
    const queue = [];
    for (let i = 0; i < numCourses; i++) {
        if (inDegree[i] === 0) {
            queue.push(i);
        }
    }
    
    // Step 5: Track the number of courses that have been processed
    let processedCourses = 0;
    
    while (queue.length > 0) {
        // Remove a course from the front of the queue
        const currentCourse = queue.shift();
        processedCourses += 1;  // Increment the count of processed courses
        
        // For each course dependent on the current course
        if (graph.has(currentCourse)) {
            for (let neighbor of graph.get(currentCourse)) {
                // Decrease the in-degree (prerequisite count) of the dependent course
                inDegree[neighbor] -= 1;
                
                // If in-degree of the dependent course is 0, add it to the queue
                if (inDegree[neighbor] === 0) {
                    queue.push(neighbor);
                }
            }
        }
    }
    
    // Step 6: If all courses have been processed, return true, else return false
    return processedCourses === numCourses;
};

Solution in Java

Java

import java.util.*;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // Step 1: Create an adjacency list to represent the graph
        List<List<Integer>> graph = new ArrayList<>();
        // Step 2: Create an array to track the in-degree (number of incoming edges) of each course
        int[] inDegree = new int[numCourses];
        
        // Initialize the graph with empty lists for each course
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        
        // Step 3: Fill the graph and in-degree array
        for (int[] pair : prerequisites) {
            int course = pair[0];
            int prereq = pair[1];
            graph.get(prereq).add(course);
            inDegree[course] += 1;
        }
        
        // Step 4: Initialize a queue with courses that have no prerequisites (in-degree of 0)
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        // Step 5: Track the number of courses that have been processed
        int processedCourses = 0;
        
        while (!queue.isEmpty()) {
            // Remove a course from the front of the queue
            int currentCourse = queue.poll();
            processedCourses += 1;  // Increment the count of processed courses
            
            // For each course dependent on the current course
            for (int neighbor : graph.get(currentCourse)) {
                // Decrease the in-degree (prerequisite count) of the dependent course
                inDegree[neighbor] -= 1;
                
                // If in-degree of the dependent course is 0, add it to the queue
                if (inDegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }
        
        // Step 6: If all courses have been processed, return true, else return false
        return processedCourses == numCourses;
    }
}

Solution in C#

C#

using System;
using System.Collections.Generic;

public class Solution {
    public bool CanFinish(int numCourses, int[][] prerequisites) {
        // Step 1: Create an adjacency list to represent the graph
        List<List<int>> graph = new List<List<int>>();
        // Step 2: Create an array to track the in-degree (number of incoming edges) of each course
        int[] inDegree = new int[numCourses];
        
        // Initialize the graph with empty lists for each course
        for (int i = 0; i < numCourses; i++) {
            graph.Add(new List<int>());
        }
        
        // Step 3: Fill the graph and in-degree array
        foreach (var pair in prerequisites) {
            int course = pair[0];
            int prereq = pair[1];
            graph[prereq].Add(course);
            inDegree[course]++;
        }
        
        // Step 4: Initialize a queue with courses that have no prerequisites (in-degree of 0)
        Queue<int> queue = new Queue<int>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.Enqueue(i);
            }
        }
        
        // Step 5: Track the number of courses that have been processed
        int processedCourses = 0;
        
        while (queue.Count > 0) {
            // Remove a course from the front of the queue
            int currentCourse = queue.Dequeue();
            processedCourses++;  // Increment the count of processed courses
            
            // For each course dependent on the current course
            foreach (int neighbor in graph[currentCourse]) {
                // Decrease the in-degree (prerequisite count) of the dependent course
                inDegree[neighbor]--;
                
                // If in-degree of the dependent course is 0, add it to the queue
                if (inDegree[neighbor] == 0) {
                    queue.Enqueue(neighbor);
                }
            }
        }
        
        // Step 6: If all courses have been processed, return true, else return false
        return processedCourses == numCourses;
    }
}

207. Course Schedule – Leetcode Solutions

Description

Solution in Python

Explanation:

Time Complexity:

Space Complexity:

Solution in Javascript

Solution in Java

Solution in C#

Popular

155. Min Stack – Leetcode Solutions

179. Largest Number – Leetcode Solutions

172. Factorial Trailing Zeroes – Leetcode Solutions

185. Department Top Three Salaries – Leetcode Solutions

5. Longest Palindromic Substring – Leetcode Solutions

18. 4Sum – Leetcode Solutions

33. Search in Rotated Sorted Array – Leetcode Solutions

207. Course Schedule – Leetcode Solutions

Description

Solution in Python

Explanation:

Time Complexity:

Space Complexity:

Solution in Javascript

Solution in Java

Solution in C#

Related Post

Popular