Course Schedule

LeetCode 207 | Difficulty: Medium

Medium

Problem 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] = [a~i~, b~i~] indicates that you must take course b~i~ first if you want to take course a~i~.

- 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.

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.

Constraints:

- `1 <= numCourses <= 2000`

- `0 <= prerequisites.length <= 5000`

- `prerequisites[i].length == 2`

- `0 <= a~i~, b~i~ < numCourses`

- All the pairs prerequisites[i] are **unique**.

Topics: Depth-First Search, Breadth-First Search, Graph Theory, Topological Sort

---

Approach

BFS (Graph/Matrix)

Use a queue to explore nodes level by level. Start from source node(s), visit all neighbors before moving to the next level. BFS naturally finds shortest paths in unweighted graphs.

When to use

Shortest path in unweighted graph, level-order processing, spreading/flood fill.

Graph Traversal

Model the problem as a graph (nodes + edges). Choose BFS for shortest path or DFS for exploring all paths. For dependency ordering, use topological sort (Kahn's BFS or DFS with finish times).

When to use

Connectivity, shortest path, cycle detection, dependency ordering.

---

Solutions

Solution 1: C# (Best: 128 ms)

Metric	Value
Runtime	128 ms
Memory	28.8 MB
Date	2020-11-12

Solution

public class Solution {
    public bool CanFinish(int numCourses, int[][] prerequisites) {
        
{
    int[] indegree = new int[numCourses];
    Queue<int> queue = new Queue<int>();
    foreach (int[] pair in prerequisites)
    {
        indegree[pair[0]]++;
    }
    for (int i = 0; i < indegree.Length; i++)
    {
        if (indegree[i] == 0)
        {
            queue.Enqueue(i);
        }
    }
    while (queue.Count != 0)
    {
        numCourses--;
        int course = queue.Dequeue();
        foreach (int[] pair in prerequisites)
        {
            if (pair[1] == course)
            {
                indegree[pair[0]]--;
                if (indegree[pair[0]] == 0)
                {
                    queue.Enqueue(pair[0]);
                }
            }
        }
    }
    return numCourses == 0;
}
    } 
}

📜 1 more C# submission(s)

Submission (2020-01-28) — 144 ms, 28.2 MB

public class Solution {
    public bool CanFinish(int numCourses, int[][] prerequisites) {
        
{
    int[] indegree = new int[numCourses];
    Queue<int> queue = new Queue<int>();
    foreach (int[] pair in prerequisites)
    {
        indegree[pair[1]]++;
    }
    for (int i = 0; i < indegree.Length; i++)
    {
        if (indegree[i] == 0)
        {
            queue.Enqueue(i);
        }
    }
    while (queue.Count != 0)
    {
        numCourses--;
        int course = queue.Dequeue();
        foreach (int[] pair in prerequisites)
        {
            if (pair[0] == course)
            {
                indegree[pair[1]]--;
                if (indegree[pair[1]] == 0)
                {
                    queue.Enqueue(pair[1]);
                }
            }
        }
    }
    return numCourses == 0;
}
    } 
}

---

Complexity Analysis

Approach	Time	Space
Graph BFS/DFS	$O(V + E)$	$O(V)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Ask about graph properties: directed/undirected, weighted/unweighted, cycles, connectivity.
• LeetCode provides 3 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.

Hint 2: Topological Sort via DFS - A great tutorial explaining the basic concepts of Topological Sort.

Hint 3: Topological sort could also be done via BFS.