LeetCode 1559: Detect Cycles in 2D Grid

Explanation:

To solve this problem, we can perform a depth-first search (DFS) on the grid while keeping track of the visited cells and the path length. We can mark each visited cell with a unique marker during the DFS traversal to avoid revisiting them within the same cycle. If we encounter a cell that is already marked as visited, and the path length is greater than or equal to 4, we have found a cycle of the same value in the grid.

Algorithmic Idea:

1. Implement a DFS function that takes the current cell coordinates, the previous cell coordinates, the current path length, and the grid as parameters.
2. Mark the current cell as visited with a unique marker to avoid revisiting it during the same cycle.
3. Recursively explore the neighboring cells in all four directions (up, down, left, right) if they have the same value as the current cell.
4. If we encounter a cell that is already visited and the path length is greater than or equal to 4, return true indicating the presence of a cycle.
5. Continue DFS traversal until all cells are visited or a cycle is found.
6. If no cycle is found after traversing all cells, return false.

Time Complexity:

The time complexity of this approach is O(m*n) where m is the number of rows and n is the number of columns in the grid.

Space Complexity:

The space complexity of this approach is O(m*n) for the visited array used to mark cells as visited.

class Solution {
    public boolean containsCycle(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] visited = new int[m][n];
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (visited[i][j] == 0 && dfs(grid, i, j, -1, -1, visited)) {
                    return true;
                }
            }
        }
        
        return false;
    }
    
    private boolean dfs(char[][] grid, int i, int j, int prevI, int prevJ, int[][] visited) {
        int m = grid.length;
        int n = grid[0].length;
        
        visited[i][j] = 1;
        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        
        for (int[] dir : dirs) {
            int newI = i + dir[0];
            int newJ = j + dir[1];
            
            if (newI >= 0 && newI < m && newJ >= 0 && newJ < n && grid[newI][newJ] == grid[i][j] && !(newI == prevI && newJ == prevJ)) {
                if (visited[newI][newJ] == 1 || dfs(grid, newI, newJ, i, j, visited)) {
                    return true;
                }
            }
        }
        
        visited[i][j] = 2;
        return false;
    }
}