210.course-schedule-ii.md

210. Course Schedule II

This is a follow-up problem of 207. Course Schedule, we need to return the order of courses that we can take to finish all courses. The key idea was explained in 207. Course Schedule, we can use the same approach to solve this problem.

BFS (Kahn's Algorithm)

• In-degree = number of prerequisites for a course.
• We start with all nodes that have in-degree 0 (no prerequisites).
• When we process a node, we reduce the in-degree of its neighbors by 1.
• If a node's in-degree becomes 0, we add it to the queue.
• We repeat this process until the queue is empty.
• If we can't process all nodes (i.e., there's a cycle), the in-degree of some nodes will be greater than 0, we return an empty array.

In this approach, we don't need to use a visited set to avoid re-visit because:

• We only enqueue a node when its in-degree hits 0 for the first time. (Either the initial value is 0 or we've finished all the prerequisites).
• Once it's enqueued, we won't enqueue it again because we never increment in-degree again.

So indegree acts as an implicit visited set.

fun findOrder(numCourses: Int, prerequisites: Array<IntArray>): IntArray {
    val courseMap = hashMapOf<Int, HashSet<Int>>()
    val indegree = IntArray(numCourses)

    for (p in prerequisites) {
        val after = p[0]
        val before = p[1]
        if (!courseMap.containsKey(before)) courseMap[before] = hashSetOf<Int>()
        courseMap[before]!!.add(after)
        indegree[after]++
    }

    val queue = ArrayDeque<Int>()
    // We enqueue all course that don't need the prerequisite.
    for (i in 0 until numCourses) {
        if (indegree[i] == 0) queue.addLast(i)
    }

    val results = mutableListOf<Int>()
    while (queue.isNotEmpty()) {
        val course = queue.removeFirst()
        results.add(course)
        courseMap[course]?.forEach { adj ->
            indegree[adj]--
            // If we finish all the prerequisites, then we can take that course.
            if (indegree[adj] == 0) {
                queue.addLast(adj)
            }
        }
    }

    for (i in 0 until numCourses) {
        if (indegree[i] > 0) return intArrayOf()
    }
    // Or we can check if the results size is equal to numCourses, if not, then there is a cycle.
    return results.toIntArray()
}

• Time Complexity: O(|V| + |E|).
  • Building adjacency list + indegree array: O(E)
  • Initializing queue: O(V)
  • BFS traversal: O(V + E)
• Space Complexity: O(|V| + |E|).
  • Adjacency list: O(V + E)
  • Indegree array: O(V)
  • Queue: O(V)
  • Result list: O(V)

DFS

enum class VisitState { NOT_VISIT, VISITED, FINISHED }
// Topological sort order
private val order = ArrayDeque<Int>()

fun findOrder(numCourses: Int, prerequisites: Array<IntArray>): IntArray {
    val graph = Array(numCourses) { mutableSetOf<Int>() }
    prerequisites.forEach { pair -> graph[pair[1]].add(pair[0])}

    val visitState = Array(numCourses) { VisitState.NOT_VISIT }
    for (n in 0 until graph.size) {
        if (visitState[n] == VisitState.NOT_VISIT) {
            if (dfs(graph, n, visitState)) return intArrayOf()
        }
    }
    return order.toIntArray()
}

// Return true if there is a cycle, otherwise return false.
private fun dfs(graph: Array<MutableSet<Int>>, i: Int, visitState: Array<VisitState>): Boolean {
    if (visitState[i] == VisitState.FINISHED) return false
    if (visitState[i] == VisitState.VISITED) return true
    visitState[i] = VisitState.VISITED
    graph[i].forEach { adj ->
        if (dfs(graph, adj, visitState)) {
            return true
        }
    }
    visitState[i] = VisitState.FINISHED
    order.addFirst(i) // Please note that we add at first, so the result is in reverse order.
    return false
}

• Time Complexity: O(|V| + |E|).

  • We visit every vertex once and explore each outgoing edge exactly once.
  • Building adjacency list: O(E)
  • DFS on all nodes: O(V + E)
    • Visiting each node: O(V)
    • Traversing all edges: O(E)

• (Optional if we use ArrayDeque or LinkedList to store the result) Reversing the result list: O(V)

• Space Complexity: O(|V| + |E|).

  • Adjacency list: O(E)
  • Visit state array: O(V)
  • Result list: O(V)
  • Recursion stack: O(V)