Coding Interview Questions | Course Schedule

January 16th, 2024

Course Schedule Problem Introduction:

This summary will talk about my solution to the course schedule problem as seen on leetcode here. A synopsis of the problem summary will be shown below:

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array of 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.

How do you solve the Course Schedule Problem using Topological Sort?

Solution:

function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  const inDegrees: number[] = Array(numCourses).fill(0);
  const graph: Map<number, number[]> = new Map();

  // Build the in-degree and adjacency list graph
  for (const [course, prerequisite] of prerequisites) {
    inDegrees[course]++;
    if (!graph.has(prerequisite)) {
      graph.set(prerequisite, []);
    }
    graph.get(prerequisite)!.push(course);
  }

  // Initialize a queue with courses having in-degree 0
  const queue: number[] = [];
  for (let i = 0; i < numCourses; i++) {
    if (inDegrees[i] === 0) {
      queue.push(i);
    }
  }

  // Perform topological sorting
  while (queue.length > 0) {
    const current = queue.shift()!;
    const neighbors = graph.get(current) || [];

    for (const neighbor of neighbors) {
      inDegrees[neighbor]--;
      if (inDegrees[neighbor] === 0) {
        queue.push(neighbor);
      }
    }
  }

  // Check if all courses can be finished (in-degrees are 0)
  return inDegrees.every((degree) => degree === 0);
}

Course Schedule Solution Summary:

Below is a breakdown of the key aspects of the solution above for the Course Schedule problem:

  1. Graph Construction:

    • In-Degree and Adjacency List: The algorithm begins by constructing the in-degree array (inDegrees) and an adjacency list graph (graph). It iterates through the prerequisites, updating the in-degrees for each course and creating a directed edge in the graph from the prerequisite to the course.

  2. Topological Sorting with Queue:

    • Initialization and Queue: The algorithm initializes a queue with courses having an in-degree of 0. This ensures that courses with no prerequisites are considered first. The in-degree array keeps track of the number of prerequisites for each course.
    • Topological Sorting: The algorithm performs topological sorting by dequeuing a course, reducing the in-degrees of its neighbors, and enqueuing neighbors with in-degrees reaching 0. This process continues until the queue is empty.

  3. Check for Course Completion:

    • Completion Check: After topological sorting, the algorithm checks if all courses can be finished. It does so by verifying if all in-degrees are 0. If any in-degree is non-zero, it indicates a cycle or a course with unresolved prerequisites.

Complexities:

  • Time Complexity: The time complexity is determined by the iterations through the prerequisites and the topological sorting. It is denoted as O(V + E), where V is the number of courses and E is the number of prerequisites.

  • Space Complexity: The space complexity is influenced by the in-degree array, adjacency list graph, and the queue. It is denoted as O(V + E), where V is the number of courses and E is the number of prerequisites.