LeetCode Entry

802. Find Eventual Safe States

12.07.2023 medium 2023 kotlin

List of nodes not in cycles

802. Find Eventual Safe States medium blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/273

Problem TLDR

List of nodes not in cycles

Intuition

Simple Depth-First Search will give optimal \(O(n)\) solution. When handling the visited set, we must separate those in cycle and safe.

Approach

  • we can remove from cycle set and add to safe set in a post-order traversal

Complexity

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

  • Space complexity: \(O(n)\)

Code


fun eventualSafeNodes(graph: Array<IntArray>): List<Int> {
    val cycle = mutableSetOf<Int>()
        val safe = mutableSetOf<Int>()
            fun cycle(curr: Int): Boolean {
                return if (safe.contains(curr)) false else !cycle.add(curr)
                || graph[curr].any { cycle(it) }
                .also {
                    if (!it) {
                        cycle.remove(curr)
                        safe.add(curr)
                    }
                }
            }
            return graph.indices.filter { !cycle(it) }
        }