[Leetcode] 207. Course Schedule

https://leetcode.com/problems/course-schedule/?envType=problem-list-v2&envId=7p5x763&sorting=W3sic29ydE9yZGVyIjoiREVTQ0VORElORyIsIm9yZGVyQnkiOiJGUkVRVUVOQ1kifV0%3D&page=1

initial

its typical topo sort

sol

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int n = numCourses;
        int[] indegree= new int[n];
        List<List<Integer>> graph = new ArrayList<>();
        for(int i=0; i<n;i++) graph.add(new ArrayList<>());

        for(int[] pre: prerequisites){
            int before = pre[1], after = pre[0];
            indegree[after]+=1;
            graph.get(before).add(after);
        }
        Queue<Integer> queue = new LinkedList<>();
        for(int i =0; i<n;i++){
            if(indegree[i]==0) queue.offer(i);
        }
        int count=0;
        while(!queue.isEmpty()){
            int node = queue.poll();
            count+=1;
            for(int neigh: graph.get(node)){
                indegree[neigh]-=1;
                if(indegree[neigh]==0) queue.offer(neigh);
            }
        }
        return count==n;
    }
}

complexity

Let me break down the time complexity step by step:

O(V + E) breakdown:

1. Building adjacency list: O(E)

   for (int[] prereq : prerequisites) {  // Loop E times
       graph.get(prereq[1]).add(prereq[0]);  // O(1)
       indegree[prereq[0]]++;               // O(1)
   }

   • We iterate through all E prerequisites exactly once

2. Finding initial zero in-degree courses: O(V)

   for (int i = 0; i < numCourses; i++) {  // Loop V times
       if (indegree[i] == 0) {             // O(1)
           queue.offer(i);                 // O(1)
       }
   }

   • We check all V courses exactly once

3. BFS processing: O(V + E)

   while (!queue.isEmpty()) {
       int course = queue.poll();              // This happens V times total
       processedCourses++;
       
       for (int dependent : graph.get(course)) {  // This inner loop runs E times total
           indegree[dependent]--;
           if (indegree[dependent] == 0) {
               queue.offer(dependent);
           }
       }
   }

   • Outer loop: Each course is processed exactly once → V iterations total
   • Inner loop: Each edge is traversed exactly once → E iterations total across all outer loop iterations

Key insight: Even though there's a nested loop, we don't multiply V × E. Each edge is only processed once when we visit its source node, so the inner loop runs a total of E times across the entire algorithm, not E times per node.

Total: O(E) + O(V) + O(V + E) = O(V + E)

so time and space is also v+e