1559.detect-cycles-in-2d-grid.md

1559. Detect Cycles in 2D Grid

TODO: Review the notes + implementations

DFS

We can traverse with the same character, and if we visit a cell that has been visited in the current traversal, then we find a cycle. But we have to prevent visiting the last cell we visited:

                next
                 |
last cell --> current --> next
                 |
                next

       <--X-- current // We can't visit the last cell in the next traversal

fun containsCycle(grid: Array<CharArray>): Boolean {
    val m = grid.size
    val n = grid[0].size
    val allVisited = HashSet<Pair<Int, Int>>()
    for (i in 0 until m) {
        for (j in 0 until n) {
            if (allVisited.contains(i to j).not()) {
                val visited = HashSet<Pair<Int, Int>>()
                if (dfs(grid, -1, -1, i, j, grid[i][j], visited)) {
                    return true
                }
                allVisited.addAll(visited)
            }
            
        }
    }
    return false
}

private fun dfs(
    grid: Array<CharArray>, 
    prevX: Int, prevY: Int,
    x: Int, y: Int, 
    c: Char, 
    visited: HashSet<Pair<Int, Int>>
): Boolean {
    val m = grid.size
    val n = grid[0].size
    if (visited.contains(x to y)) {
        return true
    }
    visited.add(x to y)
    directions.forEach { d -> 
        val newX = x + d[0]
        val newY = y + d[1]
        if (newX in 0 until m && 
            newY in 0 until n && 
            (newX != prevX || newY != prevY) &&
            grid[newX][newY] == c) 
        {
            if (dfs(grid, x, y, newX, newY, c, visited)) {
                return true
            }
        }
    }
    return false
}

• Time Complexity: O(m * n).
• Space Complexity: O(m * n).