Detect Cycles in 2D Grid

What the problem is really asking

We are given a 2D grid of characters. We need to decide whether there is any cycle of length at least 4 that walks only through cells sharing the same character, moving up, down, left, or right, and never immediately revisiting the previous cell.

The "length at least 4" and "cannot revisit the previous cell" rules together rule out the trivial two-cell back-and-forth. They do not rule out any real cycle.

Turning the grid into a graph

Treat every cell as a node. Connect two cells with an undirected edge when they are adjacent and share the same character.

With this view, the question becomes very familiar:

Does this undirected graph contain a cycle?

Why Union Find fits perfectly

For any undirected graph, Union Find gives a clean cycle check:

• For every edge (u, v), try to merge the components of u and v.
• If u and v are already in the same component, this edge closes a cycle.

We can walk the grid in row-major order. For each cell (i, j), we only need to look at two earlier neighbors:

• the cell above at (i - 1, j)
• the cell to the left at (i, j - 1)

This guarantees that each edge is processed exactly once.

Mapping 2D to 1D

Union Find is indexed by a single integer. We map cell (i, j) to the flat index i * n + j, where n is the number of columns.

• the cell above maps to (i - 1) * n + j
• the cell to the left maps to i * n + j - 1

Approach

1. Initialize Union Find with m * n nodes, each in its own set.
2. For every cell (i, j):
   • if the cell above exists and has the same character, try to union the two indices. A failed union means we found a cycle, return true.
   • if the cell to the left exists and has the same character, try to union the two indices. A failed union means we found a cycle, return true.
3. If the full scan finishes without a failed union, return false.

Path compression plus union by size keeps every operation effectively constant time.

class Solution {
    private int[] parent;
    private int[] size;

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

        for (int i = 0; i < m * n; i++) {
            parent[i] = i;
            size[i] = 1;
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i > 0 && grid[i][j] == grid[i - 1][j]) {
                    if (!union(i * n + j, (i - 1) * n + j)) {
                        return true;
                    }
                }
                if (j > 0 && grid[i][j] == grid[i][j - 1]) {
                    if (!union(i * n + j, i * n + j - 1)) {
                        return true;
                    }
                }
            }
        }

        return false;
    }

    private int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    private boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY) {
            return false;
        }

        if (size[rootX] < size[rootY]) {
            int temp = rootX;
            rootX = rootY;
            rootY = temp;
        }

        parent[rootY] = rootX;
        size[rootX] += size[rootY];
        return true;
    }
}

Dry run

Take:

grid = [
  ['a', 'a', 'a', 'a'],
  ['a', 'b', 'b', 'a'],
  ['a', 'b', 'b', 'a'],
  ['a', 'a', 'a', 'a']
]

Walk the grid top to bottom, left to right. For every 'a' cell, the neighbor above or to the left is also 'a', so we keep merging them into one giant component.

When we reach (3, 3), the cell (2, 3) above is already in the same component as (3, 2) to its left, because the whole outer ring of 'a' cells was merged earlier. The union at (3, 3) therefore fails, and we return true.

Example 3 from the prompt:

grid = [
  ['a', 'b', 'b'],
  ['b', 'z', 'b'],
  ['b', 'b', 'a']
]

Here the 'b' cells form a shape that looks like it might loop, but the only two diagonals through 'b' need exactly four 'b' cells around the center 'z'. The available 'b' cells along the ring are never all connected into a cycle because the top-left 'a' and bottom-right 'a' break the ring. No union ever fails, so the answer is false.

Why it is enough to look up and left

When we reach cell (i, j), the cells above and to the left have already been processed. Any edge from (i, j) to a later cell will be processed when that later cell is reached.

So the pair of checks

• up: (i - 1, j) with (i, j)
• left: (i, j - 1) with (i, j)

covers each edge of the graph exactly once. Every time we "fail" a union, we have identified a real cycle.

Why DFS works too

Another classic approach is to run DFS from each unvisited cell, tracking the parent so we do not use the "last edge" to mark the neighbor as visited again. If DFS encounters an already-visited cell that is not the parent, a cycle exists.

Union Find is usually easier to get right because it avoids the "previous cell" bookkeeping. The DSU version also fits naturally into one pass over the grid.

Common mistakes

1. Forgetting the direction rule

The prompt forbids stepping back to the cell you just came from. If you model this as an undirected graph, that rule is automatically respected. A single edge never forms a cycle on its own, so the "length at least 4" requirement falls out for free.

2. Checking all four neighbors in each cell

That double counts every edge. Checking only the up and left neighbors is enough, and it keeps each edge inside the algorithm exactly once.

3. Skipping path compression or union by size

Without them, worst case cost per operation grows from effectively constant to O(log n) or worse, which can be too slow on 500 x 500 grids.

Complexity

Let m be the number of rows and n be the number of columns.

Time Complexity: O(m * n * alpha(m * n))

Each cell triggers at most two union operations. With path compression and union by size, each operation is effectively constant.

Space Complexity: O(m * n)

Union Find stores one parent and one size entry per cell.