Course Schedule medium

Problem Statement

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] means to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

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.

Steps to Solve

1. Build the Graph: Represent the courses and their prerequisites as a directed graph. Each course is a node, and a directed edge from course b to course a indicates that b is a prerequisite for a.
2. Detect Cycles: Use Depth-First Search (DFS) to detect cycles in the graph. A cycle indicates that there's a circular dependency between courses, making it impossible to complete all courses.
3. Track Visited Nodes: Use two sets to track visited nodes during DFS: visited (nodes currently being visited) and completed (nodes whose traversal is complete). A node in both visited and completed means there's no cycle involving that node.
4. Return Result: If DFS detects a cycle, return false. Otherwise, return true.

Explanation

The key idea is to use topological sorting. A topological sort is a linear ordering of nodes in a directed acyclic graph (DAG) such that for every directed edge from node A to node B, node A appears before node B in the ordering. If a topological sort is possible, then it's possible to complete all courses. If a cycle exists, a topological sort is not possible. Our DFS approach effectively detects cycles while implicitly attempting a topological sort.

Code (C#)

using System;
using System.Collections.Generic;

public class Solution {
    public bool CanFinish(int numCourses, int[][] prerequisites) {
        // Create adjacency list to represent the graph
        List<int>[] graph = new List<int>[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new List<int>();
        }
        foreach (int[] pre in prerequisites) {
            graph[pre[1]].Add(pre[0]); // Add directed edge from prerequisite to course
        }

        // Sets to track visited and completed nodes
        HashSet<int> visited = new HashSet<int>();
        HashSet<int> completed = new HashSet<int>();

        // DFS function to detect cycles
        bool dfs(int course) {
            if (visited.Contains(course)) return false; // Cycle detected
            if (completed.Contains(course)) return true; // Already processed

            visited.Add(course);
            foreach (int neighbor in graph[course]) {
                if (!dfs(neighbor)) return false; // Cycle found in neighbor
            }
            visited.Remove(course);
            completed.Add(course);
            return true;
        }

        // Check for cycles starting from each node
        for (int i = 0; i < numCourses; i++) {
            if (!dfs(i)) return false;
        }
        return true; 
    }
}

Complexity Analysis

• Time Complexity: O(V + E), where V is the number of courses (vertices) and E is the number of prerequisites (edges). This is because the DFS visits each node and edge at most once.
• Space Complexity: O(V), primarily due to the visited and completed sets and the adjacency list representation of the graph. In the worst case, all vertices might be in these sets simultaneously.