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.

Flowchart Walkthrough

To determine the appropriate algorithm for LeetCode problem 1559, "Detect Cycles in 2D Grid", let's step through the Flowchart for algorithm selection:

Is it a graph?

  • Yes: The 2D grid can be considered a graph where each cell is a node, and edges exist between adjacent cells.

Is it a tree?

  • No: Since the grid can have cycles, it is not necessarily a tree which by definition does not have cycles.

Is the problem related to directed acyclic graphs (DAGs)?

  • No: The problem specifically involves detecting cycles, meaning the graph isn't acyclic.

Is the problem related to shortest paths?

  • No: This issue is centered around detecting cycles, not calculating shortest paths.

Does the problem involve connectivity?

  • Yes: Detecting cycles in a grid deals with understanding the connections between nodes (cells) to see if a path leads back to itself.

Is the graph weighted?

  • No: Connections in the grid are uniform and unweighted as each edge merely connects adjacent cells.

Conclusion: As per the flowchart, this connectivity problem in an unweighted grid leads us towards using Depth-First Search (DFS) for effectively detecting cycles. DFS is ideal here because it can continuously track paths and detect when a path loops back on itself, essential for identifying cycles.

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.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

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

1class Solution:
2    def containsCycle(self, grid: List[List[str]]) -> bool:    
3        def find(parent, x):
4            # Path compression technique which updates the parent
5            # reference of x to its root parent if x is not the root.
6            if parent[x] != x:
7                parent[x] = find(parent, parent[x])
8            return parent[x]
9
10        def union(parent, x, y):
11            # Union method to merge two subsets into a single subset
12            # by setting the parent of one element to the other.
13            parent[find(parent, x)] = find(parent, y)
14
15        rows, cols = len(grid), len(grid[0])
16        parent = list(range(rows * cols))  # Initialize each cell's parent to itself
17      
18        # Iterate over each cell in the grid
19        for i in range(rows):
20            for j in range(cols):
21                # Only check rightward and downward to avoid redundancy
22                for d_row, d_col in [[0, 1], [1, 0]]:
23                    x, y = i + d_row, j + d_col
24                    # Check if the next cell is within the grid and has the same value
25                    if x < rows and y < cols and grid[x][y] == grid[i][j]:
26                        # Convert the 2D indices to 1D to manage them in the union-find structure
27                        cell_id = i * cols + j
28                        next_cell_id = x * cols + y
29                        # If the two cells are already connected, it means there is a cycle
30                        if find(parent, next_cell_id) == find(parent, cell_id):
31                            return True
32                        # If they are not connected, union them
33                        union(parent, next_cell_id, cell_id)
34      
35        # If no cycle is found after the union-find algorithm, return False
36        return False
37
1class Solution {
2    // Array to keep track of the root parent for each cell in the grid
3    private int[] parent;
4
5    // Method to determine if the grid contains a cycle
6    public boolean containsCycle(char[][] grid) {
7        int rows = grid.length;
8        int cols = grid[0].length;
9        parent = new int[rows * cols];
10
11        // Initially, each cell is its own parent
12        for (int i = 0; i < parent.length; ++i) {
13            parent[i] = i;
14        }
15
16        // Directions array to explore right and down neighbors
17        int[] directions = {0, 1, 0};
18
19        // Iterate through each cell in the grid
20        for (int i = 0; i < rows; ++i) {
21            for (int j = 0; j < cols; ++j) {
22                // Only check right and down directions to avoid recheck and counting the edge twice
23                for (int k = 0; k < 2; ++k) {
24                    int neighborX = i + directions[k];
25                    int neighborY = j + directions[k + 1];
26
27                    // Inside grid bounds and characters match
28                    if (neighborX < rows && neighborY < cols && grid[i][j] == grid[neighborX][neighborY]) {
29                        int currentRoot = find(i * cols + j);
30                        int neighborRoot = find(neighborX * cols + neighborY);
31
32                        // Same root found implies a cycle
33                        if (currentRoot == neighborRoot) {
34                            return true;
35                        }
36
37                        // Union operation: Assign the root of the neighbor to the current cell's root
38                        parent[neighborRoot] = currentRoot;
39                    }
40                }
41            }
42        }
43
44        // No cycle found
45        return false;
46    }
47
48    // Recursive method to find the root parent for a cell with path compression
49    private int find(int cellIndex) {
50        if (parent[cellIndex] != cellIndex) {
51            parent[cellIndex] = find(parent[cellIndex]);
52        }
53        return parent[cellIndex];
54    }
55}
56
1#include <vector>
2
3class Solution {
4public:
5    std::vector<int> parent;
6
7    // Function to check if the given grid contains a cycle
8    bool containsCycle(std::vector<std::vector<char>>& grid) {
9        int numRows = grid.size();
10        int numCols = grid[0].size();
11      
12        // Initialize the parent array for union-find
13        parent.resize(numRows * numCols);
14        for (int i = 0; i < parent.size(); ++i) {
15            parent[i] = i;
16        }
17      
18        // Directions for moving right or down
19        std::vector<int> directions = {0, 1, 0};
20      
21        // Iterate through each cell in the grid
22        for (int i = 0; i < numRows; ++i) {
23            for (int j = 0; j < numCols; ++j) {
24                // Check right and down neighbors
25                for (int k = 0; k < 2; ++k) {
26                    int x = i + directions[k];
27                    int y = j + directions[k + 1];
28                  
29                    // If the neighbor is within the grid and the characters match,
30                    // check for a cycle using union-find.
31                    if (x < numRows && y < numCols && grid[x][y] == grid[i][j]) {
32                        if (findSet(x * numCols + y) == findSet(i * numCols + j)) {
33                            // Cycle found
34                            return true;
35                        }
36                        // Union the cell with its neighbor.
37                        parent[findSet(x * numCols + y)] = findSet(i * numCols + j);
38                    }
39                }
40            }
41        }
42      
43        // No cycle found
44        return false;
45    }
46
47    // Recursive function to find the root of the set that 'x' belongs to
48    int findSet(int x) {
49        if (parent[x] != x) {
50            parent[x] = findSet(parent[x]);  // Path compression
51        }
52        return parent[x];
53    }
54};
55
1/**
2 * This function checks if the given grid contains a cycle.
3 * It uses the Disjoint Set Union (DSU) structure to detect cycles in the grid.
4 * 
5 * @param {string[][]} grid - The grid represented by a 2D array of characters.
6 * @return {boolean} - Returns true if the grid contains a cycle, otherwise false.
7 */
8function containsCycle(grid: string[][]): boolean {
9    const rows: number = grid.length;
10    const cols: number = grid[0].length;
11
12    // Parent array for DSU
13    let parent: number[] = Array.from({ length: rows * cols }, (_, i) => i);
14
15    // Function to find the parent of a given node
16    function findParent(index: number): number {
17        if (parent[index] !== index) {
18            parent[index] = findParent(parent[index]);
19        }
20        return parent[index];
21    }
22
23    // Directions to move in the grid (right and down)
24    const directions: number[] = [0, 1, 0];
25
26    // Iterating through each cell in the grid
27    for (let i = 0; i < rows; ++i) {
28        for (let j = 0; j < cols; ++j) {
29            // Check only right and down direction to avoid redundant comparisons
30            for (let k = 0; k < 2; ++k) {
31                const x: number = i + directions[k];
32                const y: number = j + directions[k + 1];
33
34                // Check if the adjacent cell in the grid has the same value
35                if (x < rows && y < cols && grid[x][y] === grid[i][j]) {
36                    // Find parents of the adjacent cell and the current cell
37                    const currentCellParent: number = findParent(i * cols + j);
38                    const adjacentCellParent: number = findParent(x * cols + y);
39
40                    // If both parents are same, a cycle is detected
41                    if (currentCellParent === adjacentCellParent) {
42                        return true;
43                    }
44
45                    // Union operation: merge two sets
46                    parent[adjacentCellParent] = currentCellParent;
47                }
48            }
49        }
50    }
51
52    // No cycle found after checking all cells
53    return false;
54}
55

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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What's the relationship between a tree and a graph?


Recommended Readings