# 13.07.2023 [802. Find Eventual Safe States]

List of nodes not in cycles

13.07.2023

802. Find Eventual Safe States medium
blog post

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) }
        }