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:
-
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.
-
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.
-
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.
-
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.
-
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 returnfalse
.
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:
-
Initialization:
- We create a 1D representation of the grid in an array
p
where each cell has an indexi * n + j
, corresponding to its row and column in the grid (wherem
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.
- We create a 1D representation of the grid in an array
-
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.
-
Finding and Union Operations:
- We check if the current cell (
grid[i][j]
) is equal to an adjacent cell (eithergrid[i+1][j]
orgrid[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
.
- We check if the current cell (
-
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.
- During the
-
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.
-
Returning the Result:
- If we complete all iterations without finding a cycle, we return
false
.
- If we complete all iterations without finding a cycle, we return
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 EvaluatorExample 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 arrayp
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) withgrid[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) andgrid[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) andgrid[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.
What's the relationship between a tree and a graph?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements