Course Schedule I

Time: O(V+E)

Space: O(V+E)

Intuition

Can all courses be completed? This is cycle detection in a directed graph. If the prerequisite graph is a DAG (no cycles), all courses can be done.

Algorithm

1Build directed adjacency list: prerequisiteâ†’course.
2Topological sort (Kahn's BFS): compute in-degrees. Queue nodes with in-degree 0. Process: reduce neighbors' in-degree, add to queue when 0.
3If processed count == numCourses, return true.

Example Walkthrough

Input: n=2, prerequisites=[[1,0]]

1.Graph: 0â†’1. in-degree: [0,1]. Queue:[0]. Process 0â†’in[1]=0â†’add 1. Count=2=n.

Output: true

Common Pitfalls

•Also solvable with DFS cycle detection (white/grey/black coloring).

Course Schedule I.java

Java

// Approach: Topological sort with cycle detection (BFS Kahn's algorithm). If all nodes processed, no cycle exists.
// Time: O(V+E) Space: O(V+E)

import java.util.*;

class Solution {

    public boolean canFinish(int n, int[][] prerequisites) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }

        int[] indegree = new int[n];

        for (int[] pre : prerequisites) {
            int course = pre[0];
            int prereq = pre[1];

            adj.get(prereq).add(course);
            indegree[course]++;
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                q.offer(i);
            }
        }

        int count = 0;

        while (!q.isEmpty()) {
            int curr = q.poll();
            count++;
            for (int neighbor : adj.get(curr)) {
                indegree[neighbor]--;

                if (indegree[neighbor] == 0) {
                    q.offer(neighbor);
                }
            }
        }

        return count == n;
    }
}

Was this solution helpful?