LeetCode Entry

207. Course Schedule

13.07.2023 medium 2023 kotlin

If none edges in a cycle

207. Course Schedule medium blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/274

Problem TLDR

If none edges in a cycle

Intuition

To detect cycle, we can use DFS and two sets cycle and safe. Or use Topological Sort and check that all elements are visited.

Approach

Let’s use Topological Sort with Breadth-First Search.

  • build indegree - number of input nodes for each node
  • add to BFS only nodes with indegree[node] == 0
  • decrease indegree as it visited

Complexity

  • Time complexity: \(O(VE)\)

  • Space complexity: \(O(E + V)\)

Code


fun canFinish(numCourses: Int, prerequisites: Array<IntArray>): Boolean {
    val fromTo = mutableMapOf<Int, MutableSet<Int>>()
        val indegree = IntArray(numCourses)
        prerequisites.forEach { (to, from) ->
            fromTo.getOrPut(from) { mutableSetOf() } += to
            indegree[to]++
        }
        return with(ArrayDeque<Int>()) {
            addAll((0 until numCourses).filter { indegree[it] == 0 })
            generateSequence { if (isEmpty()) null else poll() }.map {
                fromTo[it]?.forEach {
                    if (--indegree[it] == 0) add(it)
                }
            }.count() == numCourses
        }
    }