207. Course Schedule

MediumDepth-First SearchBreadth-First SearchGraphTopological Sort
Leetcode Link

Problem Description

The problem gives us numCourses total number of courses, each labeled uniquely from 0 to numCourses - 1. We are also given an array of course pairs for prerequisites, where each pair [a, b] signifies that course a requires course b as a prerequisite. The goal is to determine if it is possible to complete all the courses fulfilling their respective prerequisites.

To simplify: imagine you have a list of courses, each with dependencies on other courses. You can only take a course if all of its prerequisite courses have been completed. You need to figure out if you can schedule these courses in such a way that all can be finished.

Flowchart Walkthrough

Let's analyze LeetCode 207. Course Schedule using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

  • Yes: The problem is modeled through prerequisites which can be represented as a directed graph where each course is a node, and a directed edge between two nodes (courses) reflects a prerequisite relationship.

Is it a tree?

  • No: Since it might contain cycles due to the prerequisite relationships, and multiple nodes might not have any incoming edges, it is not a tree.

Is the problem related to directed acyclic graphs (DAGs)?

  • Yes: The problem fundamentally involves determining if a cycle exists in the graph, which is a characteristic issue in directed acyclic graphs (DAGs).

Is the problem related to topological sorting?

  • Yes: One of the main ways to solve this is to see if a topological ordering of the courses is possible (which would be impossible if there's a cycle).

Conclusion: The flowchart guides us to use topological sort, commonly implemented via Depth-First Search (DFS), to solve this problem. DFS is helpful in detecting cycles in a directed graph and establishing a valid topological order where possible.

Intuition

The intuition behind the solution is based on detecting a possible cyclic dependency among the courses which would make it impossible to complete all of them. If there's a cycle, you would be in a situation where to take course X you need to have completed course Y, but course Y similarly requires course X. This deadlock prevents completion of the courses.

To solve this, we use topoogical sorting based on Kahn's algorithm, which is a strategy for sorting nodes in a directed graph. This approach works well here because prerequisites create a directed graph where courses are nodes and dependencies are edges.

Breaking down the intuition step by step:

  1. We construct a directed graph where each node is a course, and edges represent prerequisites (a directed edge from course b to course a means b is a prerequisite for a).
  2. We count incoming edges (indegrees) for each node. If a node/course has no incoming edges, it means there are no prerequisites, and it can be taken immediately.
  3. We repeatedly pick and remove nodes with no incoming edges (representing courses with all prerequisites completed or no prerequisites at all) and remove all edges from these nodes to other nodes (simulating taking the course and fulfilling those prerequisites).
  4. If we manage to remove all nodes (take all courses), then it's possible to finish all courses.

In more technical terms:

  • We are using a graph (specifically a directed graph) to represent the dependencies between courses.
  • A defaultdict is used to keep track of what courses depend on a given course.
  • An array indeg maintains the count of prerequisites (incoming edges) for each course.
  • A queue (deque) helps in processing the courses with zero incoming edges (prerequisites).
  • We traverse the graph starting from nodes with zero indegrees, repeatedly reducing the indegrees of the dependent nodes and adding them to the queue when their indegre becomes zero.
  • If we process (cnt) the same number of courses as are given by numCourses, we return true; else, a cycle must exist, and we return false.

Learn more about Depth-First Search, Breadth-First Search, Graph and Topological Sort patterns.

Solution Approach

The solution approach is genuinely inspired by the topological sorting algorithm. It uses several data structures and algorithms to implement the logic described in the Intuition section.

Here are the main points of the implementation, outlined step by step:

  1. Graph Representation:

    • A defaultdict for adjacency list representation of our directed graph: g = defaultdict(list).
    • Each course is a node, and each element in the list represents the adjacent nodes. For example, if course b is a prerequisite for course a, then a will be in the adjacency list of b.

  2. In-Degree Array:

    • An array indeg that represents the in-degree of each node (number of prerequisites for each course): indeg = [0] * numCourses.
    • Whenever a prerequisite relation (edge) is added, we increment the in-degree count for course a.

  3. Building the Graph and In-Degree Array:

    • We iterate through the prerequisites list, for each pair [a, b] we:
      • Add a to the adjacency list of b: g[b].append(a)
      • Increase the in-degree of a: indeg[a] += 1

  4. Processing Nodes with Zero In-Degrees:

    • A queue q using deque is initialized with all courses that have zero in-degree.
    • cnt variable is initialized to count the number of courses that we've been able to schedule (process).

  5. Topological Sort:

    • While our queue q is not empty, we process the nodes (courses) inside our queue:
      • i = q.popleft(): we get a course i from the queue.
      • cnt += 1: increment our counter as we are able to take course i.
      • For each adjacent course j in our graph (g[i]):
        • Decrease the in-degree of j: indeg[j] -= 1
        • If the in-degree of j becomes zero, it means all prerequisites of j are satisfied, and we can add j to our queue: q.append(j)

  6. Return Value:

    • After the whole process, if cnt matches numCourses, it means we were able to find a way to take all courses, and we return true.
    • If cnt does not match numCourses, it implies there are courses with prerequisites that form a cycle so we could not process them, and we return false.

This algorithm efficiently determines whether all courses can be taken by making sure all nodes are processed, ensuring that there are no directed cycles in our graph which would indicate an impossible situation with mutual prerequisites.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use a small example to illustrate the solution approach.

Suppose we have numCourses = 4 and prerequisites = [[1,0],[2,0],[3,1],[3,2]]. This means we have 4 courses labeled 0 to 3. The prerequisites are that course 1 requires course 0, course 2 requires course 0, and course 3 requires both courses 1 and 2.

Following the steps of the solution approach:

  1. Graph Representation:

    • Initialize the graph g and have courses 0 to 3 without any edges.
    • It will look like this: g = {0:[], 1:[], 2:[], 3:[]} before adding prerequisites.

  2. In-Degree Array:

    • Initialize the in-degree array indeg to have all zeros since we haven't accounted for any prerequisites yet: indeg = [0, 0, 0, 0].

  3. Building the Graph and In-Degree Array:

    • Add prerequisites to the graph. After iterating through the prerequisites, g will look like this:
      • g = {0:[1,2], 1:[3], 2:[3], 3:[]}
      • The in-degree array indeg will be [0, 1, 1, 2] indicating the number of courses each course is waiting on.

  4. Processing Nodes with Zero In-Degrees:

    • Initialize the queue q with courses that have an in-degree of 0: q = deque([0]).
    • The cnt variable is set to 0.

  5. Topological Sort:

    • Process the queue:
      • Pop course 0. We can take the course 0 because it has no prerequisites.
      • Increment cnt to 1.
      • Reduce the in-degree of courses dependent on course 0 (1 and 2), so indeg becomes [0, 0, 0, 2].
      • Since courses 1 and 2 now have an in-degree of 0, add them to q: q = deque([1,2]).
    • Continue processing:
      • Pop course 1. Increment cnt to 2.
      • Reduce the in-degree of course 3 (dependent on course 1), now indeg is [0, 0, 0, 1].
      • Do not add anything to queue as no new courses have an in-degree of 0.
      • Pop course 2. Increment cnt to 3.
      • Again, reduce the in-degree of course 3, indeg now becomes [0, 0, 0, 0].
      • Add course 3 to q since it now has an in-degree of 0: q = deque([3]).
    • Finally:
      • Pop course 3. Increment cnt to 4.

  6. Return Value:

    • Now, cnt is 4 which is equal to numCourses indicating we have been able to find an order to take all courses without getting stuck in a cycle.
    • Return true.

Thus, we can confirm that it is indeed possible to complete all the courses fulfilling their respective prerequisites with this particular example.

Solution Implementation

1from collections import defaultdict, deque
2
3class Solution:
4    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
5        # Create a graph in adjacency list format
6        graph = defaultdict(list)
7      
8        # Initialize indegree array to count prerequisites for each course
9        indegrees = [0] * numCourses
10      
11        # Build the graph and fill indegrees based on prerequisites
12        for course, prereq in prerequisites:
13            graph[prereq].append(course)  # Add course to prereq's adjacency list
14            indegrees[course] += 1        # Increment indegree of the course
15      
16        # Start with courses that have no prerequisites
17        queue = deque([i for i in range(numCourses) if indegrees[i] == 0])
18      
19        # Counter for number of courses with no remaining prerequisites
20        completed_count = 0
21      
22        # Process courses in topological order
23        while queue:
24            # Pop a course with no remaining prerequisites
25            course = queue.popleft()
26            completed_count += 1
27          
28            # Decrease the indegree of course's successors
29            for successor in graph[course]:
30                indegrees[successor] -= 1
31              
32                # If successor now has no prerequisites, add to queue
33                if indegrees[successor] == 0:
34                    queue.append(successor)
35      
36        # If all courses have been completed, return True, otherwise False
37        return completed_count == numCourses
38
1class Solution {
2    public boolean canFinish(int numCourses, int[][] prerequisites) {
3        // Create a graph represented by an adjacency list where each course points to its prerequisites
4        List<List<Integer>> graph = new ArrayList<>();
5        for (int i = 0; i < numCourses; i++) {
6            graph.add(new ArrayList<>());
7        }
8
9        // Create an array to store the in-degree (number of prerequisites) for each course
10        int[] inDegrees = new int[numCourses];
11
12        // Populate the graph and update the in-degrees based on the prerequisites
13        for (int[] prerequisite : prerequisites) {
14            int course = prerequisite[0];
15            int prerequisiteCourse = prerequisite[1];
16            graph.get(prerequisiteCourse).add(course);
17            inDegrees[course]++; // Increment the in-degree of the course
18        }
19
20        // Queue to hold courses with in-degree of 0 (no prerequisites)
21        Deque<Integer> queue = new ArrayDeque<>();
22
23        // Enqueue all courses which have no prerequisites
24        for (int i = 0; i < numCourses; i++) {
25            if (inDegrees[i] == 0) {
26                queue.offer(i);
27            }
28        }
29
30        // Counter for number of courses that have been processed
31        int processedCourses = 0;
32
33        // Process the courses in the queue
34        while (!queue.isEmpty()) {
35            int course = queue.poll();
36            processedCourses++; // Increment count of processed courses
37
38            // Iterate over the neighbors of the current course
39            for (int neighbor : graph.get(course)) {
40                // Decrement the in-degree of each neighbor, since we have processed one of their prerequisites
41                inDegrees[neighbor]--;
42                if (inDegrees[neighbor] == 0) {
43                    // If in-degree becomes 0, it means all prerequisites are met, so enqueue the course
44                    queue.offer(neighbor);
45                }
46            }
47        }
48
49        // If the number of processed courses equals the total number of courses, all can be finished
50        return processedCourses == numCourses;
51    }
52}
53
1class Solution {
2public:
3    // Function to determine if all courses can be finished
4    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
5        vector<vector<int>> graph(numCourses); // A graph where each node is a course
6        vector<int> inDegree(numCourses); // Indegree array to keep track of prerequisites
7      
8        // Process prerequisites to build the graph and update indegrees
9        for (auto& prerequisite : prerequisites) {
10            int course = prerequisite[0];
11            int prereq = prerequisite[1];
12            graph[prereq].push_back(course); // Add an edge from prereq to course
13            ++inDegree[course]; // Increment indegree of the course
14        }
15      
16        queue<int> noPrereqCourses; // Queue to store courses with no prerequisites
17        for (int i = 0; i < numCourses; ++i) {
18            if (inDegree[i] == 0) {
19                noPrereqCourses.push(i); // Enqueue if no prerequisites
20            }
21        }
22      
23        int finishedCount = 0; // Counter for finished courses
24        while (!noPrereqCourses.empty()) {
25            int current = noPrereqCourses.front();
26            noPrereqCourses.pop();
27            ++finishedCount; // Increment finished courses whenever one is completed
28          
29            // Reduce indegree for all neighbors, if it drops to 0, enqueue
30            for (int neighbor : graph[current]) {
31                if (--inDegree[neighbor] == 0) {
32                    noPrereqCourses.push(neighbor);
33                }
34            }
35        }
36      
37        // If we have not finished all courses, return false; otherwise, true
38        return finishedCount == numCourses;
39    }
40};
41
1function canFinish(numCourses: number, prerequisites: number[][]): boolean {
2    // Create an adjacency list to represent the graph of courses
3    const adjacencyList: number[][] = new Array(numCourses).fill(0).map(() => []);
4  
5    // Array to store the in-degree (number of dependencies) of each course
6    const inDegrees: number[] = new Array(numCourses).fill(0);
7  
8    // Fill the adjacency list and in-degree array based on prerequisites
9    for (const [course, prerequisite] of prerequisites) {
10        adjacencyList[prerequisite].push(course);
11        inDegrees[course]++;
12    }
13
14    // Queue for courses with no prerequisites (in-degree of 0)
15    const queue: number[] = [];
16  
17    // Initialize the queue with courses that have no prerequisites
18    for (let i = 0; i < numCourses; ++i) {
19        if (inDegrees[i] === 0) {
20            queue.push(i);
21        }
22    }
23
24    // Counter for the number of courses with satisfied prerequisites
25    let count = 0;
26
27    // Process the queue until it's empty
28    while (queue.length) {
29        // Remove the first course from the queue
30        const currentCourse = queue.shift()!;
31      
32        // Increment the count of courses that can be taken
33        count++;
34
35        // Decrease the in-degree of the adjacent courses and
36        // add them to the queue if they have no other prerequisites
37        for (const adjacentCourse of adjacencyList[currentCourse]) {
38            if (--inDegrees[adjacentCourse] === 0) {
39                queue.push(adjacentCourse);
40            }
41        }
42    }
43
44    // Compare the count of courses taken to the total number of courses
45    return count === numCourses;
46}
47

Time and Space Complexity

Time Complexity

The time complexity of the given algorithm can be analyzed as follows:

  • Building the graph (g) and the indegree array (indeg) involves iterating over all of the edges in the prerequisites list. If there are E edges (prerequisites), this part takes O(E) time.

  • Creating the initial queue q with all courses that have 0 indegree requires iterating over the indegree array once, which takes O(V) time, where V is the number of courses (numCourses).

  • The while loop processes each node (course) exactly once and reduces the indegree of its neighbors. Since it examines the indegree and enqueues nodes, this loop operates across all V nodes and E edges in the worst case. Therefore, the loop runs in O(V + E) time.

  • The combined time complexity of all the above components is O(E) + O(V) + O(V + E), which simplifies to O(V + E).

Thus, the overall time complexity of the function is O(V + E).

Space Complexity

The space complexity is determined by the space required for the graph (g), the indegree array (indeg), and the queue (q):

  • The graph g can potentially hold all V vertices with E edges in the adjacency list representation, which requires O(V + E) space.

  • The indegree array indeg requires O(V) space as it holds an entry for each of the numCourses.

  • The queue q in the worst case can hold all V vertices, which requires O(V) space.

The space required for cnt and other primitive variables is O(1) and, therefore, negligible in the analysis.

Adding up the space complexities for g, indeg, and q gives O(V + E) + O(V) + O(V), which simplifies to O(V + E) since V is often much less than E for dense graphs, and therefore can be absorbed by O(E).

In conclusion, the space complexity of the function is O(V + E).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Recommended Readings

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

Graph Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could

Want a Structured Path to Master System Design Too? Don’t Miss This!