Leetcode 1559. Detect Cycles in 2D Grid

Problem explanation:

This problem presents us with a 2D grid (m x n) made up of lowercase English letters. The aim is to detect if there is any cycle in the grid. A cycle is defined as a path of length 4 or more that starts and ends at the same cell. You can move from a cell to any of its four adjacent cells (up, down, left, right) as long as it has the same value as the current cell. However, the condition is that you cannot move to the cell which you visited last. If such a cycle exists, we need to return true, otherwise return false.

Let's go through an example:

grid = [["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]]

In the above example, we can find several valid cycles. The 'a's in the first row form a cycle as well as the 'a's in the fourth row. Additionally, the 'a's in the first and fourth columns also form valid cycles. Thus, we can return true.

Solution:

To solve this problem, we can use Graph Traversal algorithms. Depth-First Search (DFS) is a very good pick for detecting cycles in a graph. DFS will go as far as possible along each branch before backtracking.

The general approach for the solution class in various languages will involve the following:

  1. First, we'll initialize a m x n boolean grid, seen, to keep track of the cells that we've visited.
  2. We'll traverse through the entire grid. For every cell that we visit, which has not been visited before, we'll conduct a DFS to attempt to find a cycle.
  3. In our DFS implementation, we'll first mark the current cell as visited. Then, for every adjacent cell in the four possible directions (up, down, left, right), we will check if the adjacent cell has the same value, and if it is not the cell from where we just arrived. If it fulfills these conditions, and it has been visited before, it means we found a cycle and we return true. Otherwise, we'll conduct DFS on this cell.
  4. If we finish the DFS and did not find a cycle, we return false.

Python Solution:

1
2python
3class Solution:
4    def containsCycle(self, grid: List[List[str]]) -> bool:
5        seen = set()
6        def dfs(i, j, pi, pj):
7            if (i, j) in seen:
8                return True
9
10            seen.add((i, j))
11            for ni, nj in [(i-1,j),(i+1,J),(i,j-1),(i,j+1)]:
12                if 0 <= ni < len(grid) and 0 <= nj < len(grid[0]) and (ni, nj) != (pi, pj) and grid[ni][nj] == grid[i][j]:
13                    if dfs(ni, nj, i, j): 
14                        return True
15            return False
16
17        for i in range(len(grid)):
18            for j in range(len(grid[0])):
19                if (i, j) not in seen and dfs(i, j, None, None):
20                    return True
21        return False

In the Python implementation above, we use Depth-First Search (dfs) function to find a cycle. If dfs function returns true, then the grid contains a cycle. If it doesn't, we continue traversal until we've visited all the cells. If the dfs function never returns true while traversing the entire grid, then we return False indicating that the grid contains no cycle.

Each of the similar solutions in Java, JavaScript, C++, and C# follow the same DFS algorithm.## Javascript Solution:

1
2javascript
3class Solution {
4    constructor() {
5        this.dx = [-1, 0, 1, 0];
6        this.dy = [0, 1, 0, -1];
7        this.n = 0;
8        this.m = 0;
9        this.grid = [];
10        this.visited = []
11    }
12    
13    containsCycle(grid) {
14        this.grid = grid;
15        this.n = grid.length;
16        this.m = grid[0].length;
17        this.visited = Array(this.n).fill().map(() => Array(this.m).fill(false));
18       
19        for (let i = 0; i < this.n; i++) {
20            for (let j = 0; j < this.m; j++) {
21                if (!this.visited[i][j] && this.dfs(i, j, -1, -1))
22                    return true;
23            }
24        }
25    return false;
26    }
27    
28    dfs(x, y, fx, fy) {
29        this.visited[x][y] = true;
30        for (let i = 0; i < 4; i++) {
31            let nx = x + this.dx[i];
32            let ny = y + this.dy[i];
33            if (nx < 0 || nx >= this.n || ny < 0 || ny >= this.m || (this.grid[nx][ny] !== this.grid[x][y]))
34                continue;
35            if (!this.visited[nx][ny]) {
36                if (this.dfs(nx, ny, x, y))
37                    return true;
38            } 
39            else if (nx !== fx || ny !== fy) {
40                return true;
41            }
42        }
43    return false;
44    }
45}

In the Javascript solution, we are following a similar DFS algorithm. The containsCycle() method iterates over each cell and if cell is not visited yet, it calls dfs() to check for cycle. In dfs() the four directions are checked and if any of the four directions of any cell forms a cycle (visited and having the same value as its parent cell), the function returns true. The containsCycle() function will return false only if no cell results in a cycle.

Java Solution:

1
2java
3public class Solution {
4    int n, m;
5    int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
6    public boolean containsCycle(char[][] grid) {
7        this.n = grid.length;
8        this.m = grid[0].length;
9        boolean[][] seen = new boolean[n][m];
10        for (int i=0; i<n; i++) {
11            for (int j=0; j<m; j++) {
12                if (!seen[i][j]) {
13                    if (dfs(i, j, -1, -1, grid, seen)) {
14                        return true;
15                    }
16                }
17            }
18        }
19        return false;
20    }
21    private boolean dfs(int x, int y, int px, int py, char[][] grid, boolean[][] seen) {
22        seen[x][y] = true;
23        for (int[] d : dir) {
24            int nx= x + d[0], ny = y + d[1];
25            if(nx >= 0 && nx < n && ny >= 0 && ny < m) {
26                if (!(nx == px && ny == py) && grid[nx][ny] == grid[x][y]) {
27                    if (seen[nx][ny] || dfs(nx, ny, x, y, grid, seen)){
28                        return true;
29                    }
30                }
31            }
32        }
33        return false;
34    }
35}

In the Java solution, we are also using a boolean grid seen with the same size as the input grid to mark cells as visited or not. In the containsCycle function, we traverse through the entire grid and if any cell has not been visited, we launch the DFS algorithm on that cell, if dfs function call returns true we return true else we continue to next cell. If we finish traversing the entire grid and no cycle is detected, we return false.


Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ