207.course-schedule.md

207. Course Schedule

Clarification Questions

1. Are all the prerequisites pair unique?
2. What if prerequisites is empty? (but numCourses is 1 or greater than 1)
3. Do all the prerequisite pairs cover all courses from 0 to numCourses - 1.

DFS

The courses forms a directed graph, and the prerequisites forms the edges of the graph. If the graph has a cycle, then we can't finish all the courses. Otherwise, the courses can be topologically sorted.

The problem is equivalent to detect a cycle in a directed graph. If there exists a cycle, then we can't find the topological sort. We define the state of a node as NOT_VISITED, VISITED and FINISHED, and we can detect a cycle if we visit a node that is in VISITED state.

const val NOT_VISITED = 0
const val VISITED = 1 
const val FINISHED = 2      // No cycle

fun canFinish(n: Int, prerequisites: Array<IntArray>): Boolean {
    val graph = buildGraph(n, prerequisites)
    val visited = IntArray(n) { NOT_VISITED }
    for (i in 0 until n) {
        if (visited[i] == NOT_VISITED) {
            if (dfs(graph, i, visited).not()) return false
        }
    }
    return true
}

private fun dfs(graph: Array<HashSet<Int>>, i: Int, visited: IntArray): Boolean {
    if (visited[i] == FINISHED) return true
    if (visited[i] == VISITED) return false
    visited[i] = VISITED
    graph[i].forEach { adj ->
        if (dfs(graph, adj, visited).not()) return false
    }
    visited[i] = FINISHED
    return true
}

private fun buildGraph(n: Int, prerequisites: Array<IntArray>): Array<HashSet<Int>> {
    val graph = Array(n) { HashSet<Int>() }
    for (p in prerequisites) {
        val from = p[1]
        val to = p[0]
        graph[from].add(to)
    }
    return graph
}

• Time Complexity: O(V + E), V is the number of courses, V is the number of prerequisites.
• Space Complexity: O(V + E), we build a adjacent list that takes O(V + E), and enqueue all courses that takes O(n).

BSF (Kahn's Algorithm)

BFS approach track the in-degree of every node: for a course (node), the indegrees represents how many prerequisites we have to take before so that we can finish the current one.

For example, the prerequisites is [[2, 0], [2, 1]], that means that I have to finish course 0 and 1 so that I can finish 2, that can be represented in graph like this:

0 -> 2
1 -> 2

So course (node) 2 has 2 indegree edges, and the number of indegrees is 2.

To solve this problem, we build a graph with indegree array for every courses (nodes), then:

1. Start with course having in-degree 0, that means it has no reprequisite and we can take that course now.
2. For every course we take, we decrease the indegree of the courses that have the current course as prerequisite.
3. If the indegree of a course is 0, that means we can take that course now, so we enqueue it.
4. If all courses are proceeded, then we can finish all courses.

We don't need to track the visited courses, because we only enqueue the course that we can study now, and we won't enqueue it again.

fun canFinish(numCourses: Int, prerequisites: Array<IntArray>): Boolean {
    val inDegrees = IntArray(numCourses)
    val graph = Array<HashSet<Int>>(numCourses) { hashSetOf<Int>() }
    for (p in prerequisites) {
        graph[p[1]].add(p[0])
        inDegrees[p[0]]++
    }
    
    val queue = ArrayDeque<Int>()
    for (i in 0 until numCourses) {
        // Queue enques all the course that we can study now. (no or finished all prerequisites)
        if (inDegrees[i] == 0) {
            queue.addLast(i)
        }
    }
    var count = 0
    while (queue.isNotEmpty()) {
        val course = queue.removeFirst()
        count++
        // Find all courses after the current course
        graph[course].forEach { adj -> 
            inDegrees[adj]--
            // If all prerequiistes are finished, then I can study this after course.
            if (inDegrees[adj] == 0) queue.addLast(adj)
        }
    }
    return count == numCourses
}

(Optinal) If we track the visited courses, we can use the visited array to avoid enqueue the course that we've already enqueued. It's OK to add to visited when we enqueue the course if we track visited, because we only enqueue the course that we can study now, and we won't enqueue it again.

for (i in 0 until n) {
    if (indegree[i] == 0) {
        queue.addLast(i)
        visited[i] = true
    }
}
while (queue.isNotEmpty()) {
    val i = queue.removeFirst()
    graph[i].forEach { adj -> 
        if (indegree[adj] > 0) {
            indegree[adj]--
            if (indegree[adj] == 0) {
                queue.addLast(adj)
                visited[adj] = true
            }
        }
    }
}

• Time Complexity: As same as DFS.
• Space Complexity: As same as DFS.