Detect Cycles in 2D Grid: Union-Find on a Matrix

You are given an m x n grid of characters. Your task is to determine whether the grid contains a cycle. A cycle is a path of length 4 or more in the grid such that the start and end cells are the same, every consecutive pair of cells in the path are adjacent (up, down, left, right), and every cell in the path shares the same character.

This is LeetCode 1559: Detect Cycles in 2D Grid. At first glance it looks like a DFS problem, but Union-Find gives you a cleaner solution with less room for error.

Why this problem matters

This problem sits at the intersection of two important patterns: grid-to-graph conversion and cycle detection with Union-Find. Most developers learn cycle detection through DFS with parent tracking, which works but requires careful bookkeeping to avoid revisiting the cell you just came from. Union-Find sidesteps that complexity entirely. You process edges one by one, and the moment two nodes that are already connected get another edge between them, you know there is a cycle.

Understanding Union-Find cycle detection on a grid also prepares you for problems like redundant connections, network connectivity, and any scenario where you need to incrementally build components while watching for loops.

The key insight

Think of each cell as a node in a graph. For every cell, look at its right neighbor and its bottom neighbor. If a neighbor has the same character, that pair forms an edge. Now the problem reduces to: does this graph of same-character edges contain a cycle?

Union-Find makes this simple. As you scan the grid left-to-right, top-to-bottom, you try to union each cell with its right and bottom neighbors (when they share the same character). If two cells already have the same root before you union them, they are already connected through some other path. Adding this edge would create a cycle.

By only checking right and bottom neighbors, you process each edge exactly once. You never double-count, and you never need to track "where did I come from" like you would in DFS.

The solution

def contains_cycle(grid: list[list[str]]) -> bool:
    rows, cols = len(grid), len(grid[0])
    parent = list(range(rows * cols))
    rank = [0] * (rows * cols)

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(a, b):
        ra, rb = find(a), find(b)
        if ra == rb:
            return True
        if rank[ra] < rank[rb]:
            ra, rb = rb, ra
        parent[rb] = ra
        if rank[ra] == rank[rb]:
            rank[ra] += 1
        return False

    for r in range(rows):
        for c in range(cols):
            idx = r * cols + c
            if c + 1 < cols and grid[r][c] == grid[r][c + 1]:
                if union(idx, idx + 1):
                    return True
            if r + 1 < rows and grid[r][c] == grid[r + 1][c]:
                if union(idx, idx + cols):
                    return True
    return False

Let's break down each piece.

Parent array and flat indexing. We flatten the 2D grid into a 1D array. Cell (r, c) maps to index r * cols + c. Every cell starts as its own parent, meaning each cell is its own isolated component.

Find with path compression. The find function walks up the parent chain to the root. Along the way, it compresses the path by pointing each node directly at its grandparent. This keeps the tree shallow and makes future lookups nearly constant time.

Union by rank. When merging two components, we attach the shorter tree under the taller one. This prevents the tree from degenerating into a linked list. If both trees have the same rank, we pick one as root and increment its rank.

The cycle check. The key line is if ra == rb: return True inside union. If both cells already share the same root before we merge them, they are already connected. This new edge closes a loop.

Scanning right and down. We only check the neighbor to the right (c + 1) and the neighbor below (r + 1). This ensures every edge between adjacent same-character cells gets processed exactly once. If we also checked left and up, we would process each edge twice and get false positives.

Visual walkthrough

Complexity analysis

Time. We visit each cell once and perform at most two union operations per cell (right and down). Each union and find operation takes O(alpha(m * n)) amortized time, where alpha is the inverse Ackermann function. For any practical input size, alpha is at most 4, so the time is effectively O(m * n).

Space. The parent and rank arrays each have m * n entries, so space is O(m * n).

The building blocks

1. Union-Find with path compression and union by rank

The core data structure pattern that makes this solution work:

def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x

def union(a, b):
    ra, rb = find(a), find(b)
    if ra == rb:
        return True
    if rank[ra] < rank[rb]:
        ra, rb = rb, ra
    parent[rb] = ra
    if rank[ra] == rank[rb]:
        rank[ra] += 1
    return False

This pattern appears in dozens of problems: redundant connections, accounts merge, number of provinces, and more. The key is that union returns True when the two elements already share a root, which signals a cycle. You will reuse this exact template across many Union-Find problems.

2. Grid-to-graph edge enumeration

Converting a 2D grid into edges by scanning right and down neighbors:

for r in range(rows):
    for c in range(cols):
        idx = r * cols + c
        if c + 1 < cols and grid[r][c] == grid[r][c + 1]:
            process_edge(idx, idx + 1)
        if r + 1 < rows and grid[r][c] == grid[r + 1][c]:
            process_edge(idx, idx + cols)

This is the standard way to enumerate all edges in a 4-directional grid without duplicates. By only looking right and down, you guarantee each horizontal and vertical edge is visited exactly once. This same pattern works for problems like number of islands (with Union-Find), connected components in a grid, and minimum spanning tree on a grid.

Edge cases

• Single row or single column. The grid still works. You only have right neighbors (single row) or down neighbors (single column). A cycle requires at least a 2x2 block, so a single row or column of identical characters has no cycle.
• All cells the same character. Any 2x2 block forms a cycle. The algorithm catches this on the first 2x2 block it encounters.
• No two adjacent cells share a character (checkerboard pattern). No edges are ever created, so no unions happen. Return false.
• 1x1 grid. No neighbors at all. No edges, no cycle. Return false.
• Large grid with a single long chain of same characters (no branching). A chain without branching never produces a cycle because each new cell only adds one edge, extending the component without closing a loop.
• Multiple disjoint cycles. The algorithm detects the first cycle it encounters and returns true immediately. It does not need to find all of them.

From understanding to recall

You now understand why Union-Find works for cycle detection on a grid and how the right-and-down scanning avoids double-counting edges. The logic is clean when you read it. But under interview pressure, you need to write the find function with path compression, remember to return True from union when roots match, and flatten 2D coordinates into 1D indices, all without hesitation.

Spaced repetition closes that gap. You practice writing the Union-Find template and the grid scanning loop from scratch at increasing intervals. After a few rounds, the parent[x] = parent[parent[x]] path compression trick and the r * cols + c index formula become automatic. That is the difference between understanding a solution and being able to produce it.

Related posts

• Number of Islands - Grid traversal fundamentals that builds toward cycle detection in matrices
• Accounts Merge - Another Union-Find problem that groups connected components
• Course Schedule - Cycle detection in directed graphs using a different approach

CodeBricks breaks Detect Cycles in 2D Grid into its Union-Find and grid-edge-enumeration building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a Union-Find grid problem shows up in your interview, you do not hesitate. You just write it.