Keyboard shortcuts

Press or to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Course Schedule 🧠

LeetCode Link: Course Schedule

Difficulty: Medium

Problem Explanation 📝

Problem: LeetCode 207 - Course Schedule

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] = [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 course 0 you have to first take course 1. Return true if you can finish all courses. Otherwise, return false.

Intuition: This problem can be approached as a graph problem where the courses represent nodes and the prerequisites represent directed edges. To determine if it is possible to finish all courses, we need to check if there is a cycle in the graph. If there is a cycle, it means there is a dependency loop, and we cannot finish all the courses.

Approach:

  1. Build an adjacency list representation of the graph using the prerequisites.
  2. Initialize a visited array to track the visited nodes during the DFS traversal.
  3. Iterate through each node in the graph and perform a DFS traversal to detect cycles:
  • If the current node is being visited, it means there is a cycle, so return false.
  • If the current node is not visited, perform a DFS traversal on its neighbors.
  1. If no cycles are detected after the DFS traversal, return true.

Time Complexity: The time complexity is O(V + E), where V is the number of courses (nodes) and E is the number of prerequisites (edges). We visit each course and prerequisite once.

💾 Space Complexity: The space complexity is O(V + E), where V is the number of courses (nodes) and E is the number of prerequisites (edges). This is the space used for the adjacency list and the visited array.

Solutions 💡

Cpp 💻

class Solution {
  public:
    bool canFinish(int numCourses, vector<vector<int>> &prerequisites) {
        vector<vector<int>> graph(numCourses);  // Adjacency list representation of the graph
        vector<int> visited(numCourses, 0);     // Visited array to track the visited nodes

        // Build the graph
        for (const auto &prerequisite : prerequisites) {
            int course = prerequisite[0];
            int prerequisiteCourse = prerequisite[1];
            graph[course].push_back(prerequisiteCourse);
        }

        // Perform a DFS traversal to detect cycles
        for (int course = 0; course < numCourses; ++course) {
            if (!dfs(course, graph, visited)) {
                return false;
            }
        }

        return true;
    }

  private:
    bool dfs(int course, vector<vector<int>> &graph, vector<int> &visited) {
        // If the current course is being visited, it means there is a cycle
        if (visited[course] == 1) {
            return false;
        }

        // If the current course is already visited, return true
        if (visited[course] == -1) {
            return true;
        }

        visited[course] = 1;  // Mark the current course as being visited

        // Perform a DFS traversal on the neighbors
        for (const auto &neighbor : graph[course]) {
            if (!dfs(neighbor, graph, visited)) {
                return false;
            }
        }

        visited[course] = -1;  // Mark the current course as visited
        return true;
    }
};

// Topological sort
// Same time and space complexity but this can be more efficient in terms of practical performance
/*
class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);   // Adjacency list representation of the graph
        vector<int> inDegree(numCourses, 0);      // In-degree of each course

        // Build the graph and calculate the in-degree of each course
        for (const auto& prerequisite : prerequisites) {
            int course = prerequisite[0];
            int prerequisiteCourse = prerequisite[1];
            graph[prerequisiteCourse].push_back(course);
            ++inDegree[course];
        }

        queue<int> q;   // Queue to store courses with in-degree 0

        // Enqueue courses with in-degree 0
        for (int i = 0; i < numCourses; ++i) {
            if (inDegree[i] == 0) {
                q.push(i);
            }
        }

        // Perform topological sorting
        while (!q.empty()) {
            int course = q.front();
            q.pop();
            --numCourses;    // Decrement the number of remaining courses

            // Decrement the in-degree of neighbors and enqueue if their in-degree becomes 0
            for (const auto& neighbor : graph[course]) {
                if (--inDegree[neighbor] == 0) {
                    q.push(neighbor);
                }
            }
        }

        return numCourses == 0;
    }
};
*/

Python 🐍

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = {i: [] for i in range(numCourses)}
        in_degree = [0] * numCourses

        # Construct the graph and count in-degrees
        for course, prereq in prerequisites:
            graph[prereq].append(course)
            in_degree[course] += 1

        # Initialize a queue with nodes having in-degree zero
        queue = collections.deque(
            [course for course, degree in enumerate(in_degree) if degree == 0]
        )

        # Perform topological sorting and update in-degrees
        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                in_degree[neighbor] -= 1
                if in_degree[neighbor] == 0:
                    queue.append(neighbor)

        # If any course has in-degree greater than zero, there's a cycle
        return all(degree == 0 for degree in in_degree)