LeetCode 1559: Detect Cycles in 2D Grid Solution

Master LeetCode problem 1559 (Detect Cycles in 2D Grid), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1559. Detect Cycles in 2D Grid

Medium

Array Depth-First Search Breadth-First Search Union Find Matrix

Problem Explanation

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:

Implement a DFS function that takes the current cell coordinates, the previous cell coordinates, the current path length, and the grid as parameters.
Mark the current cell as visited with a unique marker to avoid revisiting it during the same cycle.
Recursively explore the neighboring cells in all four directions (up, down, left, right) if they have the same value as the current cell.
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.
Continue DFS traversal until all cells are visited or a cycle is found.
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.

Solution Code

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;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1559 (Detect Cycles in 2D Grid)?

This page provides optimized solutions for LeetCode problem 1559 (Detect Cycles in 2D Grid) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1559 (Detect Cycles in 2D Grid)?

The time complexity for LeetCode 1559 (Detect Cycles in 2D Grid) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1559 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1559 in Java, C++, or Python.

Back to LeetCode Solutions