1905.count-sub-islands.md

1905. Count Sub Islands

Traversal

We can traverse the 2nd islands and check if the cell is in the 1st island. We define dfs() function that returns true if all the cells are in the 1st island.

Please note that we don't early return in dfs() function, because we need to make sure all the cells are visited. See 130. Surrounded Regions for more details.

DFS

fun countSubIslands(grid1: Array<IntArray>, grid2: Array<IntArray>): Int {
    var count = 0
    val m = grid2.size
    val n = grid2[0].size
    val visited = HashSet<Pair<Int, Int>>()
    for (x in 0 until m) {
        for (y in 0 until n) {
            if (grid2[x][y] == 1 && visited.contains(x to y).not()) {
                val result = dfs(grid1, grid2, x, y, visited)
                if (result) {
                    count++
                }
            }
        }
    }
    return count
}

fun dfs(grid1: Array<IntArray>, 
        grid2: Array<IntArray>,
        x: Int, y: Int): Boolean {
    val m = grid2.size
    val n = grid2[0].size
    if (x !in 0 until m || y !in 0 until n || grid2[x][y] != 1) return true
    if (grid2[x][y] == visited) return true
    if (grid2[x][y] != 1) return true

    grid2[x][y] = visited
    var result = grid1[x][y] == 1
    directions.forEach { d ->
        val newX = x + d[0]
        val newY = y + d[1]
        result = dfs(grid1, grid2, newX, newY) && result
    }
    return result
}

private fun dfs(
    grid1: Array<IntArray>, 
    grid2: Array<IntArray>,
    x: Int, 
    y: Int, 
    visited: HashSet<Pair<Int, Int>>
): Boolean {
    var result = true
    // We should NOT early return here, we have to make sure all the cells 
    // are visited, even if the result is false.
    // if (grid1[x][y] == 0) return false
    if (grid1[x][y] == 0) result = false
    visited.add(x to y)
    for (dir in directions) {
        val newX = x + d[0]
        val newY = y + d[1]
        if (newX !in 0 until grid2.size || newY !in 0 until grid2[0].size) continue
        if (visited.contains(newX to newY)) continue
        if (grid2[newX][newY] != 1) continue

        // We don't also early return here, we have to make sure all the cells visited.
        // 
        // And we can't write the following code, which will short-circuit the result.
        // result = result && dfs(grid1, grid2, newX, newY, visited)
        result = dfs(grid2, newX, newY, visited, grid1) && result
    }
    return result
}

BFS

fun countSubIslands(grid1: Array<IntArray>, grid2: Array<IntArray>): Int {
    var count = 0
    val visited = HashSet<Pair<Int, Int>>()
    for (i in grid2.indices) {
        for (j in grid2[0].indices) {
            if (grid2[i][j] == 1 && visited.contains(i to j).not()) {
                if (bfs(grid1, grid2, i, j, visited)) count++
            }
        }
    }
    return count
}

private fun bfs(grid1: Array<IntArray>, 
                grid2: Array<IntArray>,
                sourceX: Int, 
                sourceY: Int,
                visited: HashSet<Pair<Int, Int>>): Boolean {
    val m = grid2.size
    val n = grid2[0].size
    val queue = ArrayDeque<Pair<Int, Int>>()
    queue.addLast(sourceX to sourceY)
    visited.add(sourceX to sourceY)
    // We don't early return here, we have to make sure all the cells visited.
    var result = grid1[sourceX][sourceY] == 1
    while (queue.isNotEmpty()) {
        val (x, y) = queue.removeFirst()
        // We check if the position of grid2 at grid1 is 1.
        result = result && (grid1[x][y] == 1)
        for (d in directions) {
            val newX = x + d[0]
            val newY = y + d[1]
            if (newX !in 0 until m || newY !in 0 until n) continue
            if (visited.contains(newX to newY)) continue
            if (grid2[newX][newY] != 1) continue
            queue.addLast(newX to newY)
            visited.add(newX to newY)
        }
    }
    return result
}

• Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the grid.
• Space Complexity: O(m * n).