algoadvance

Leetcode 207. Course Schedule

Problem Statement

You are given a total of numCourses courses you have to take, labeled from 0 to numCourses-1. You are also given a list of prerequisite pairs prerequisites where prerequisites[i] = [a_i, b_i] indicates that you must take course b_i before course a_i.

Given the total number of courses and the list of prerequisites, determine if it is possible for you to finish all courses.

Clarifying Questions

1. Q: Are there duplicate prerequisite pairs in the input? A: No, each prerequisite pair is unique.

2. Q: Can the prerequisite list contain self-dependency (e.g., [0, 0])? A: No, a course does not require itself as a prerequisite.

3. Q: What should be returned if no courses are to be taken (numCourses = 0)? A: Return true since there are no courses to complete.

Strategy

This problem can be viewed as a cycle detection problem in a directed graph. Here, courses are represented as nodes and prerequisites as directed edges.

We’ll solve this problem using two different approaches:

1. Depth-First Search (DFS)
2. Kahn’s Algorithm (BFS for Topological Sort)

For both approaches:

• Nodes represent courses.
• Edges represent prerequisites.

DFS Approach:

1. Graph Representation: Build an adjacency list from prerequisites.
2. Cycle Detection with Recursive DFS:
   • Use a visitation state array: 0 (unvisited), 1 (visiting), 2 (visited).
   • If revisiting a visiting node, a cycle is detected.

BFS Approach (Kahn’s Algorithm):

1. Graph Representation: Build an adjacency list for the graph and an array for in-degrees.
2. Topological Sort:
   • Use a queue to track nodes with zero in-degrees.
   • Process each node, decrementing in-degree of neighboring nodes.
   • If the sorted order contains all courses, there is no cycle.

Time Complexity

Both approaches have similar time complexity:

• Time Complexity: (O(V + E)), where (V) is the number of nodes (courses), and (E) is the number of edges (prerequisites).
• Space Complexity: (O(V + E)) due to the graph representation and auxiliary data structures.

Let’s implement both approaches.

Implementation in C++

DFS Approach

#include <vector>

using namespace std;

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        for (auto& prereq : prerequisites) {
            graph[prereq[1]].push_back(prereq[0]);
        }
        
        vector<int> visit(numCourses, 0);
        
        for (int i = 0; i < numCourses; ++i) {
            if (hasCycle(i, graph, visit)) {
                return false;
            }
        }
        
        return true;
    }
    
private:
    bool hasCycle(int node, const vector<vector<int>>& graph, vector<int>& visit) {
        if (visit[node] == 1) return true;
        if (visit[node] == 2) return false;
        
        visit[node] = 1;
        for (int neighbor : graph[node]) {
            if (hasCycle(neighbor, graph, visit)) {
                return true;
            }
        }
        visit[node] = 2;
        
        return false;
    }
};

BFS Approach (Kahn’s Algorithm)

#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        vector<int> inDegree(numCourses, 0);
        
        for (auto& prereq : prerequisites) {
            graph[prereq[1]].push_back(prereq[0]);
            ++inDegree[prereq[0]];
        }
        
        queue<int> q;
        for (int i = 0; i < numCourses; ++i) {
            if (inDegree[i] == 0) {
                q.push(i);
            }
        }
        
        int completedCourses = 0;
        while (!q.empty()) {
            int course = q.front();
            q.pop();
            ++completedCourses;
            
            for (int neighbor : graph[course]) {
                if (--inDegree[neighbor] == 0) {
                    q.push(neighbor);
                }
            }
        }
        
        return completedCourses == numCourses;
    }
};

Summary

• We discussed and clarified the problem requirements.
• We established two strategies: DFS for cycle detection and BFS for topological sorting.
• Time complexity for both approaches is (O(V + E)).
• Implemented both approaches in C++.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?