827.making-a-large-island.md

827. Making A Large Island

Traversal

1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
1 1 0 1 1
0 0 1 0 0
0 0 1 0 0

We calculate the area of each island and store it in a dictionary. (In our implementation, we change the cell to an index.)

flood-fill algorithm!!

A A _ _ _   A: 4
A A _ _ _   B: 1
_ _ B _ _   C: 2
C C _ D D   D: 2
_ _ E _ _   E: 2
_ _ E _ _

Then we iterate each 0's cell, we flip it to 1's and calculate the area of the island that it connects to by checking the 4 directionally-adjacent area. We sum the areas of the islands that it connects to.

A A _  //                A   B
A A 1  // new area = 1 + 4 + 1 = 6
_ _ B

_ _ B _ _  //                B   C   D   E
C C 1 D D  // new area = 1 + 1 + 2 + 2 + 2
_ _ E _ _
_ _ E _ _

But we have to avoid duplicate connecting. We can use a set to filter out what we have connected.

A A _        A
A 1 _  =>  A 1  // duplicate
A A _        A  // duplicate

    fun largestIsland(grid: Array<IntArray>): Int {
        val m = grid.size
        val n = grid[0].size
        // Pitfall: We can't start from 0 or 1, they are used in the grid.
        var index = 2
        val areaMapping = HashMap<Int, Int>()
        for (i in 0 until m) {
            for (j in 0 until n) {
                if (grid[i][j] == 1) {
                    val area = dfs(grid, i, j, index)
                    areaMapping[index] = area
                    index++
                }
            }
        }

        var maxArea = 0
        for (i in 0 until m) {
            for (j in 0 until n) {
                // Try to connect the 4 directions.
                if (grid[i][j] == 0) {
                    var area = 1
                    // We track which area is connected
                    var addedIndex = HashSet<Int>()
                    directions.forEach { d ->
                        val newX = i + d[0]
                        val newY = j + d[1]
                        if (newX in 0 until m && newY in 0 until n) {
                            val cell = grid[newX][newY]
                            if (cell !in addedIndex) {
                                addedIndex.add(cell)
                                area += (areaMapping[cell] ?: 0)
                            }
                        }
                    }
                    maxArea = maxOf(maxArea, area)
                } else {
                    // Remember to update the max area from existing islands.
                    maxArea = maxOf(maxArea, areaMapping[grid[i][j]] ?: 0)
                }
            }
        }
        return maxArea
    }

    // DFS to calculate the area, and mark the cell to `index`
    private fun dfs(grid: Array<IntArray>, x: Int, y: Int, index: Int): Int {
        val m = grid.size
        val n = grid[0].size
        if (x !in 0 until m || y !in 0 until n) return 0
        if (grid[x][y] == index || grid[x][y] == 0) return 0

        grid[x][y] = index
        var area = 1
        directions.forEach { d ->
            val newX = x + d[0]
            val newY = y + d[1]
            area += dfs(grid, newX, newY, index)
        }
        return area
    }
}

• Time Complexity: O(n^2)
• Space Complexity: O(n^2)