LeetCode Entry

1559. Detect Cycles in 2D Grid

26.04.2026 medium 2026 kotlin rust

Check cycle in 2D grid

1559. Detect Cycles in 2D Grid medium substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1340

Problem TLDR

Check cycle in 2D grid

Intuition

The trivial idea: start DFS from each position, mark visited cells, check neighbours, skip parent. Have to mark visited cells again with different mark to not do DFS on the same group later. The mark in post-order should be different to make a wall for the next group.

The little bit more interesting idea: use Union-Find. Walk row by row and connect items. If there is a cycle then right cell would be already connected.

Approach

• the G is for ‘Good’
• use path compression for Union-Find
• do you know why we don’t searching the root for the down cell in Rust?

Complexity

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

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

Code

    fun containsCycle(g: Array<CharArray>) = IntArray(g.size*g[0].size){it}
        .let { u -> u.indices.any { i -> val w = g[0].size
            fun f(x: Int): Int = if (u[x]==x) x else {u[x]=f(u[x]);u[x]}
            fun c(j: Int, G: Boolean) = G && g[j/w][j%w] == g[i/w][i%w]
                &&(f(i) == f(j) || { u[f(i)] = f(j); !G}())
            c(i+1, i%w<w-1) || c(i+w, i+w<u.size)
        }}

    pub fn contains_cycle(g: Vec<Vec<char>>) -> bool {
        let w=g[0].len(); let z=g.len()*w; let mut u:Vec<_>=(0..z).collect();
        (0..z).any(|i|{
            if i+w<z && g[i/w+1][i%w] == g[i/w][i%w] { u[i+w] = i }
            i%w<w-1 && g[i/w][i%w+1] == g[i/w][i%w] && {
                let [a,b] = [i, i+1].map(|mut x|{while x!=u[x]{u[x]=u[u[x]];x=u[x]}x});
                a == b || {u[a] = b; 0>0}
            }
        })
    }