Problem Statement in English

You’re given a 2D grid of characters. You have to determine if there is a cycle in the grid. A cycle is a path of length 4 or more in the grid that starts and ends at the same cell and consists of the same character.

If there is a cycle, return true. Otherwise, return false.

Approach

If you think about it, the grid can be thought of as a grid and a loop can be thought of as a component in a graph.

Thus, we can use union find to solve this problem.

We will iterate through the grid and for each cell, we will check its right and down neighbors. If they are the same character, we will union them.

If they are already in the same component, then we have found a cycle and we can return true. If we finish iterating through the grid and we haven’t found any cycles, we can return false.

There’s a neat little trick to encode the 2D grid into a 1D array. We can use the formula index = (row * number_of_columns) + column to encode the 2D coordinates into a single integer. This will help us in the union find implementation.

A catch here is that we only need to check the right and down neighbors to avoid checking the same pair of cells multiple times. This will incorectly identify cycles as we will be checking the same pair of cells multiple times.

And we’re done!

Solution in Python


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

        parent = [i for i in range(m * n)]
        rank = defaultdict(int)

        directions = [(0, 1), (1, 0)]

        def encode(x, y):
            return (x * n) + y

        def find(i):
            root = i
            while parent[root] != root:
                root = parent[root]

            while parent[i] != root:
                next_node = parent[i]
                parent[i] = root
                i = next_node
            return root

        def union(n1, n2):
            p1 = find(n1)
            p2 = find(n2)

            if p1 == p2:
                return True

            if rank[p1] > rank[p2]:
                parent[p2] = p1
            elif rank[p1] > rank[p2]:
                parent[p1] = p2
            else:
                parent[p1] = p2
                rank[p2] += 1

            return False

        for i in range(m):
            for j in range(n):
                for dx, dy in directions:
                    nx, ny = i + dx, j + dy

                    if 0 <= nx < m and 0 <= ny < n and grid[i][j] == grid[nx][ny]:
                        c1, c2 = encode(i, j), encode(nx, ny)
                        if union(c1, c2):
                            return True

        return False

Complexity

  • Time: $O(m \times n)$
    Since we iterate through the grid once.

  • Space: $O(m \times n)$
    Since we use a union find data structure to store the parent and rank of each cell.

And we are done.