1559. Detect Cycles in 2D Grid

Problem Description

The problem requires us to determine whether there is a cycle of the same letter within a two-dimensional array, or grid. A cycle is defined as a sequence of four or more cells that starts and ends at the same cell, with each adjacent cell in the sequence sharing the same value and being connected vertically or horizontally (not diagonally). Additionally, it is not permissible to revisit the immediately prior cell, meaning you cannot go back and forth between two cells, which would otherwise form an invalid 2-step cycle.

For example, consider the following grid where A indicates the same repeating character:

1A A A A
2A B B A
3A A A A

This would contain a cycle since you can start at the top-left corner and move right three times, then down twice, then left three times, and finally up twice to return to the starting point, all while staying on cells with the same value.

However, in the following grid, there is no such cycle:

1A A A
2B B B
3A A A

In this case, you cannot construct a path that starts and ends at the same cell without violating the movement rules.

Intuition

The intuition behind the solution involves using a graph theory algorithm known as Union-Find. This algorithm can effectively group cells into connected components. When we are considering a pair of adjacent cells with the same value, we want to determine if they belong to the same connected component which would mean they are part of a cycle.

Here's the step-by-step approach:

1. Initialize: We begin by representing the cells of the grid as nodes in a graph and initializing them as their own parents to indicate that they are in their distinct connected components.

2. Union Find Algorithm: We iterate over each cell, and when we find adjacent cells with the same value (either to the right or below to avoid redundancy), we perform the Find operation to determine the leaders of their connected components.

3. Checking for Cycles: If the leaders are the same, it means we're trying to connect two nodes that are already within the same connected component. Since we only look to the right and below, this indicates a cycle is detected.

4. Union Operation: If the leaders are different, we perform the Union operation, setting the leader of one connected component to be the leader of the other, effectively merging them.

5. Return Result: If a cycle is found in the above process, we return true. If no cycles are detected upon going through all eligible adjacent cell pairs, we return false.

Using the Union-Find algorithm ensures that we can efficiently track and merge connected components without the repetitive checking of each element. It's an optimized way to solve problems related to connectivity and cycle detection in grids or graphs.

Learn more about Depth-First Search, Breadth-First Search and Union Find patterns.

Solution Approach

The reference solution approach suggests utilizing Union-Find, which is a well-known disjoint-set data structure used in the solution to keep track of the connected components within the grid. The solution approach is broken down into its fundamental parts:

1. Initialization:

   • We create a 1D representation of the grid in an array p where each cell has an index i * n + j, corresponding to its row and column in the grid (where m is the number of rows, n is the number of columns, and starting indices at 0).
   • Initially, each cell is its own parent in the Union-Find structure, indicating that each cell is in a separate connected component.

2. Iterating Over the Cells:

   • We use a nested loop to iterate over the cells in the grid. The inner iteration considers two specific adjacencies per cell (right and bottom), to avoid duplicate checks and potential infinite recursion.

3. Finding and Union Operations:

   • We check if the current cell (grid[i][j]) is equal to an adjacent cell (either grid[i+1][j] or grid[i][j+1]) to find ones with equal values.
   • When a matching adjacent cell is found, we perform the find operation to identify the roots of the connected components for the current cell and the adjacent one. This operation follows the parent pointers until reaching the root of a set (a cell whose parent is itself).
   • After finding both roots, if they are the same, we've encountered a cell that is about to form a cycle with a previously visited cell, and we return true.

4. Path Compression:

   • During the find operation, we also employ path compression by setting each visited node's parent to the root. This flattens the structure of the tree, leading to more efficient find operations in future iterations.

5. Checking for Cycles:

   • If the roots for the current cell and its adjacent equal-value cell are different, we perform the Union operation by setting the parent of the adjacent cell's root to be the parent of the current cell's root. No cycle is immediately detected in this case.

6. Returning the Result:

   • If we complete all iterations without finding a cycle, we return false.

1class Solution:
2    def containsCycle(self, grid: List[List[str]]) -> bool:
3        def find(x):
4            if p[x] != x:
5                p[x] = find(p[x])
6            return p[x]
7
8        # Initialize Union-Find data structure.
9        m, n = len(grid), len(grid[0])
10        p = list(range(m * n))
11
12        # Iterate through each cell in the grid.
13        for i in range(m):
14            for j in range(n):
15                for a, b in [[0, 1], [1, 0]]:
16                    x, y = i + a, j + b
17                    # Check for adjacent cells with the same value.
18                    if x < m and y < n and grid[x][y] == grid[i][j]:
19                        # Find the roots of the connected components.
20                        root1 = find(x * n + y)
21                        root2 = find(i * n + j)
22                        # If the roots are the same, a cycle is detected.
23                        if root1 == root2:
24                            return True
25                        # If not, union the components.
26                        p[root1] = root2
27        # No cycle found, return false.
28        return False

The clever use of a Union-Find algorithm with path compression makes this solution efficient and effective for complex grid structures.

Example Walkthrough

Let's use a small example to illustrate the solution approach. Consider the following grid:

1A A B
2B A A
3A A A

We need to determine whether this grid contains a cycle of the same letter. Here’s how we'll apply the Union-Find algorithm:

Step 1: Initialization

• We have a grid of 3x3, so we create a Union-Find array p with 9 elements [0,1,2,3,4,5,6,7,8].

Step 2: Iterating Over the Cells

• We start with the top-left cell (0,0), and it has a right (0,1) and bottom (1,0) cell to compare with.

Step 3: Finding and Union Operations

• First, we compare grid[0][0] (A) with grid[0][1] (A), as they share the same value, we check their roots. Both roots are themselves as no unions have been performed yet, so their roots are 0 and 1, respectively.
• Since the roots are different, we perform a union by setting the root of the first cell (0) to be the parent of the second cell's root (1), now our Union-Find array p is [0,0,2,3,4,5,6,7,8].

Step 4: Path Compression

• As we only had a single union operation so far, path compression doesn't change p at this point.

Step 5: Checking for Cycles

• We move to the next pair of adjacent cells with the same values, which are grid[1][1] (A) and grid[2][1] (A). After the find operation, their roots are themselves, so no cycle is detected and we perform the union.

Step 6: Returning the Result

• As we continue with the rest of the pairs, we find adjacent cells with the same value at grid[1][2] (A) and grid[2][2] (A). After the find operation, we should have the same root for both, which indicates these cells are connected to the same component. However, since we only perform the find operation for pairs of right and bottom cells, we can't form a cycle with just two cells—it requires at least four.
• Hence, we don't find any cycles after checking all valid adjacent cells, and we return false.

1class Solution:
2    def containsCycle(self, grid: List[List[str]]) -> bool:
3        def find(x):
4            if p[x] != x:
5                p[x] = find(p[x])
6            return p[x]
7
8        # Initialize Union-Find data structure.
9        m, n = len(grid), len(grid[0])
10        p = list(range(m * n))
11
12        # Iterate through each cell in the grid.
13        for i in range(m):
14            for j in range(n):
15                # We only check right [0, 1] and down [1, 0]
16                for a, b in [[0, 1], [1, 0]]:
17                    x, y = i + a, j + b
18                    if x < m and y < n and grid[i][j] == grid[x][y]:
19                        root1 = find(i * n + j)
20                        root2 = find(x * n + y)
21                        if root1 == root2:
22                            return True
23                        p[root2] = root1
24        return False

In this example, the Union-Find algorithm allows us to efficiently traverse the grid, merging connected components and checking for cycles, ultimately finding that no cycle exists within the given grid.

Solution Implementation

Time and Space Complexity

The time complexity of the given code is O(m * n * α(m * n)), where m and n are the dimensions of the grid and α is the Inverse Ackermann function, which is a very slow-growing function and can be considered constant for all practical inputs. This time complexity comes from iterating over each cell in the grid, which is O(m * n), and performing the find operation for each adjacent cell we're inspecting, which due to path compression in the union-find data structure, has an effectively constant time complexity.

The space complexity of the code is O(m * n). This space is used to store the parent array p for each cell, which keeps track of the disjoint sets in the union-find structure. There is no additional significant space used, so the space complexity is directly proportional to the size of the grid.

Learn more about how to find time and space complexity quickly using problem constraints.