200.number-of-islands.md

200. Number of Islands

Clarification Questions

• Can we modify the input grid?

Traversal

We iterate the grid, and start to traverse if it's island, then mark every cell as visited, then we increment the count when finishing the traversal.

private val visited = hashSetOf<Pair<Int, Int>>()
private var numsOfIslands = 0 
private val visited = '#' // Mark as visited

fun numIslands(grid: Array<CharArray>): Int {
    for (i in 0 until grid.size) {
        for (j in 0 until grid[0].size) {
            if (grid[i][j] == '1') {
                dfs(grid, i, j)
                // Or bfs(grid, i, j)
                numsOfIslands++
            }
        }
    }
    return numsOfIslands
}

private fun dfs(grid: Array<CharArray>, x: Int, y: Int) {
    val m = grid.size
    val n = grid[0].size
    if (x !in 0 until m) return
    if (y !in 0 until n) return
    if (grid[x][y] != '1') return
    if (visited.contains(x to y)) return
    grid[x][y] = visited
    for (d in directions) {
        dfs(grid, x + d[0], y + d[1]) 
    }
}

private fun dfs(grid: Array<CharArray>, x: Int, y: Int) {
    val m = grid.size
    val n = grid[0].size
    grid[x][y] = visited
    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 (grid[newX][newY] == visited) continue
        if (grid[newX][newY] == '0') continue
        dfs(grid, newX, newY)
    }
}

private fun bfs(grid: Array<CharArray>, i: Int, j: Int) {
    val m = grid.size
    val n = grid[0].size
    val queue = ArrayDeque<Pair<Int, Int>>()
    queue.addLast(i to j)
    grid[i][j] = visited
    while (queue.isNotEmpty()) {
        val (x, y) = queue.removeFirst()
        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 (grid[newX][newY] == visited) continue
            if (grid[newX][newY] == '0') continue
            queue.addLast(newX to newY)
            grid[newX][newY] = visited
        }
    }
}

private fun bfs(grid: Array<CharArray>, x: Int, y: Int) {
    val queue = ArrayDeque<Pair<Int, Int>>()
    queue.addLast(x to y) 
    while (queue.isNotEmpty()) {
        val node = queue.removeFirst()
        val i = node.first
        val j = node.second
        if (i < 0 || i >= grid.size || j < 0 || j >= grid[0].size || grid[i][j] != '1' ||
                visited.contains(i to j)) continue
        grid[i][j] = visited
        directions.forEach { d ->
            val newX = i + d[0]
            val newY = j + d[1]
            queue.addLast(newX to newY)
        }
    }
}

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

Union Find

• Each cell is a node, and we union the nodes if they are connected.
• We convert (x, y) to x * n + y to used it as index in the union find array.
• Initialize the union find array with size m * n, and each cell is a root node.
• Please note that 0 is also added to union find array, so the componentCount is NOT correct numbers of islands. We have to count the number of 1s in the grid by ourselves, and decrease when two cells are unioned successfully.

fun numIslands(grid: Array<CharArray>): Int {
    val m = grid.size
    val n = grid[0].size
    val uf = UnionFind(m * n)

    // We initialize the whole grid to uf, including the `0`s. So we have to count the number of `1`s in the grid by ourselves.
    var landCount = 0
    for (x in 0 until m) {
        for (y in 0 until n) {
            if (grid[x][y] == '1') landCount++
        }
    }
    
    for (x in 0 until m) {
        for (y in 0 until n) {
            val index1 = x * n + y
            if (grid[x][y] == '1') {
                for (d in directions) {
                    val newX = x + d[0]
                    val newY = y + d[1]
                    // If there is an edge between two valid cells, we union them.
                    if (newX in 0 until m &&
                        newY in 0 until n &&
                        grid[newX][newY] == '1') {
                        val index2 = newX * n + newY
                        // If two cells are connected, we decrease the land count.
                        if (uf.union(index1, index2)) {
                            landCount--
                        }
                    }
                }
            }
        }
    }
    return landCount
}

• Time Complexity: O(m * n * α(m * n)) for union(x, y) and find(x), where α(n) is the inverse Ackermann function. It's near O(1) time. Total time complexity is O(m * n).
• Space Complexity: O(m * n).