1559. Detect Cycles in 2D Grid

/**
 * Problem: LeetCode 1559 - Detect Cycles in 2D Grid
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
class Solution {
    static class DSU {
        int[] parent;
        int[] rank;

        public DSU(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }

        public int find(int i) {
            if (parent[i] == i) return i;
            return parent[i] = find(parent[i]);
        }

        public boolean union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (rootI == rootJ) return false; // Cycle detected

            if (rank[rootI] < rank[rootJ]) {
                parent[rootI] = rootJ;
            } else if (rank[rootI] > rank[rootJ]) {
                parent[rootJ] = rootI;
            } else {
                parent[rootJ] = rootI;
                rank[rootI]++;
            }
            return true;
        }
    }

    public boolean containsCycle(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        DSU dsu = new DSU(m * n);

        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                int u = r * n + c;

                // Check right neighbor
                if (c + 1 < n && grid[r][c] == grid[r][c + 1]) {
                    int v = r * n + (c + 1);
                    if (!dsu.union(u, v)) {
                        return true;
                    }
                }

                // Check down neighbor
                if (r + 1 < m && grid[r][c] == grid[r + 1][c]) {
                    int v = (r + 1) * n + c;
                    if (!dsu.union(u, v)) {
                        return true;
                    }
                }
            }
        }

        return false;
    }
}

"""
Problem: LeetCode 1559 - Detect Cycles in 2D Grid
Difficulty: Medium
Language: Python
Author: CodeByTushu
"""
from typing import List


class DSU:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, i: int) -> int:
        if self.parent[i] == i:
            return i
        self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def union(self, i: int, j: int) -> bool:
        root_i = self.find(i)
        root_j = self.find(j)
        if root_i == root_j:
            return False  # Cycle detected

        if self.rank[root_i] < self.rank[root_j]:
            self.parent[root_i] = root_j
        elif self.rank[root_i] > self.rank[root_j]:
            self.parent[root_j] = root_i
        else:
            self.parent[root_j] = root_i
            self.rank[root_i] += 1
        return True


class Solution:
    def containsCycle(self, grid: List[List[str]]) -> bool:
        m = len(grid)
        n = len(grid[0])
        dsu = DSU(m * n)

        for r in range(m):
            for c in range(n):
                u = r * n + c

                # Check right neighbor
                if c + 1 < n and grid[r][c] == grid[r][c + 1]:
                    v = r * n + (c + 1)
                    if not dsu.union(u, v):
                        return True

                # Check down neighbor
                if r + 1 < m and grid[r][c] == grid[r + 1][c]:
                    v = (r + 1) * n + c
                    if not dsu.union(u, v):
                        return True

        return False

/**
 * Problem: LeetCode 1559 - Detect Cycles in 2D Grid
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <numeric>

using namespace std;

class Solution {
    struct DSU {
        vector<int> parent;
        vector<int> rank;

        DSU(int n) : parent(n), rank(n, 0) {
            iota(parent.begin(), parent.end(), 0);
        }

        int find(int i) {
            if (parent[i] == i) return i;
            return parent[i] = find(parent[i]);
        }

        bool unite(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (rootI == rootJ) return false; // Cycle detected

            if (rank[rootI] < rank[rootJ]) {
                parent[rootI] = rootJ;
            } else if (rank[rootI] > rank[rootJ]) {
                parent[rootJ] = rootI;
            } else {
                parent[rootJ] = rootI;
                rank[rootI]++;
            }
            return true;
        }
    };

public:
    bool containsCycle(vector<vector<char>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        DSU dsu(m * n);

        for (int r = 0; r < m; ++r) {
            for (int c = 0; c < n; ++c) {
                int u = r * n + c;

                // Check right neighbor
                if (c + 1 < n && grid[r][c] == grid[r][c + 1]) {
                    int v = r * n + (c + 1);
                    if (!dsu.unite(u, v)) {
                        return true;
                    }
                }

                // Check down neighbor
                if (r + 1 < m && grid[r][c] == grid[r + 1][c]) {
                    int v = (r + 1) * n + c;
                    if (!dsu.unite(u, v)) {
                        return true;
                    }
                }
            }
        }

        return false;
    }
};

/**
 * Problem: LeetCode 1559 - Detect Cycles in 2D Grid
 * Difficulty: Medium
 * Language: JavaScript
 * Author: CodeByTushu
 */
class DSU {
    constructor(n) {
        this.parent = new Int32Array(n);
        this.rank = new Int32Array(n);
        for (let i = 0; i < n; i++) {
            this.parent[i] = i;
        }
    }

    find(i) {
        if (this.parent[i] === i) return i;
        this.parent[i] = this.find(this.parent[i]);
        return this.parent[i];
    }

    union(i, j) {
        let rootI = this.find(i);
        let rootJ = this.find(j);
        if (rootI === rootJ) return false; // Cycle detected

        if (this.rank[rootI] < this.rank[rootJ]) {
            this.parent[rootI] = rootJ;
        } else if (this.rank[rootI] > this.rank[rootJ]) {
            this.parent[rootJ] = rootI;
        } else {
            this.parent[rootJ] = rootI;
            this.rank[rootI]++;
        }
        return true;
    }
}

/**
 * @param {character[][]} grid
 * @return {boolean}
 */
var containsCycle = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    const dsu = new DSU(m * n);

    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            const u = r * n + c;
            const ch = grid[r][c];

            // Check right neighbor
            if (c + 1 < n && ch === grid[r][c + 1]) {
                const v = r * n + (c + 1);
                if (!dsu.union(u, v)) {
                    return true;
                }
            }

            // Check down neighbor
            if (r + 1 < m && ch === grid[r + 1][c]) {
                const v = (r + 1) * n + c;
                if (!dsu.union(u, v)) {
                    return true;
                }
            }
        }
    }

    return false;
};