Problem overview
The method sizeOfIslands receives a grid of 0s and 1s as an Array[Array[Int]]. A 1 is land and a 0 is water. An island is a group of land cells connected horizontally or vertically. The method returns a List[Int] with the size of every island, in any order.
In the first example, all nine land cells are linked through side-by-side neighbors, so the result is [9]. In the second example, the 2 x 2 block in the top-left corner has 4 cells, the lone cell in row 2 has 1, and the two cells at the bottom right have 2, so the sizes are 1, 4 and 2. Diagonal contact doesn't connect cells.
Approach: find an island, count it while erasing it
Scan the grid cell by cell. The first land cell of an island that the scan meets starts a new island. To measure it, run a depth-first search (DFS) from that cell. The search visits every land cell connected to it, adds 1 to a counter for each one, and turns each visited cell into water. When the search returns, the counter holds the island's size, and since the whole island is now water, the scan can't find it again.
The DFS is recursive. For a cell it asks: is this a land cell inside the grid? If not, stop. If so, count it, turn it into water, and then try the four neighbors: up, down, left and right.
The counter lives in a field of the class, noOfCells, not inside dfs, because every recursive call adds to the same total. It is reset to 0 each time the scan starts a new island.
Step by step
- Declare the field
noOfCellsas avarset to 0 inside the class. It counts the cells of the island being explored. - Declare
resultas avarholding an emptyList[Int](). A ScalaListis immutable, so adding a size creates a new list that is assigned back toresult. - Loop over the rows with
iin0 until grid.length. - Loop over the columns with
jin0 until grid(0).length, nested inside the first loop, so every cell(i, j)is visited. - Test for land:
grid(i)(j) == 1. Scala indexes arrays with parentheses. - Reset
noOfCellsto 0 before exploring, so it counts only the island about to be explored. - Call
dfs(grid, i, j), which erases the island and counts its cells. - Append the count with
result :+ noOfCellsand assign the new list back toresult. - End with
resultafter both loops. - Write
dfswith the parametersgrid,rowandcol, returningUnit. Arrays are passed by reference, so changinggridinsidedfschanges the caller's grid. - Stop at invalid cells. If
isValidCell(grid, row, col)is false,returnat once. Water and off-grid neighbors both end the search in that direction. - Count the cell with
noOfCells += 1. - Mark it as water by assigning 0 to
grid(row)(col). Without this, two neighboring land cells would call each other forever. - Describe the four moves as an array of pairs of (row change, column change).
- Recurse on each neighbor with
row + d(0)andcol + d(1). Neighbors outside the grid can be passed as they are, because the check at the start ofdfsrejects them. - Write
isValidCell: the row is inside the grid, the column is inside the grid, and the cell is a 1, joined with&&.
The solution in Scala
class Solution {
def isValidCell(grid: Array[Array[Int]], row: Int, col: Int): Boolean = {
row >= 0 && row < grid.length &&
col >= 0 && col < grid(0).length &&
grid(row)(col) == 1
}
def dfs(grid: Array[Array[Int]], row: Int, col: Int): Unit = {
if (!isValidCell(grid, row, col)) {
return
}
noOfCells += 1
grid(row)(col) = 0
val directions = Array(Array(-1, 0), Array(1, 0), Array(0, -1), Array(0, 1))
for (d <- directions) {
dfs(grid, row + d(0), col + d(1))
}
}
var noOfCells = 0
def sizeOfIslands(grid: Array[Array[Int]]): List[Int] = {
var result = List[Int]()
for (i <- 0 until grid.length) {
for (j <- 0 until grid(0).length) {
if (grid(i)(j) == 1) {
noOfCells = 0
dfs(grid, i, j)
result = result :+ noOfCells
}
}
}
result
}
}
The Scala details worth a closer look:
- Order of members. Inside a class, methods and fields can refer to members declared later in the class body. That is why
dfscan usenoOfCellsbefore the field's line, andsizeOfIslandscan come last. - Lists are immutable.
result :+ noOfCellsdoesn't changeresult; it returns a new list with the value added at the end. That is whyresultis avarand the new list is assigned back. - Short-circuit
&&. InisValidCellthe bounds are tested beforegrid(row)(col), so an out-of-range index is never read. A line that ends with&&lets the expression continue on the next line. - Result order. The sizes come in scan order. On the second example the method returns
List(4, 1, 2), which has the same sizes as[1, 4, 2]in a different order. - The grid changes. After the call every cell of the caller's grid is 0. Copy the grid first if you still need the original.
Complexity
Let the grid have R rows and C columns.
Time: O(R * C). The scan looks at each cell once. Each land cell is counted and erased by exactly one dfs call, and every other call returns immediately. The calls total at most five per cell: one from the scan and up to four from neighbors. Appending to a List with :+ copies the list, so many tiny islands add some extra cost, but the total stays small compared with the grid scan.
Space: O(R * C) in the worst case. The recursion can go as deep as the island is large. With the JVM's default stack size, a grid of all land a few hundred cells on each side can be enough to overflow it. An explicit stack or a queue avoids this limit.
Edge cases and common mistakes
- Empty grid. An empty array returns
List(): the outer loop never runs, sogrid(0)is never read. - All water.
Array(Array(0, 0))returnsList(). - All land.
[[1,1],[1,1]]returnsList(4). - Diagonal cells.
[[1,0,1],[0,1,0],[1,0,1]]returns five islands of size 1, because corners don't connect. - Not resetting the counter. Without
noOfCells = 0, each island's count would include all earlier islands. - Marking the cell too late. If the cell isn't turned into water before the recursive calls, the search comes back to it from its neighbors and never ends.
- Reading before checking. Putting
grid(row)(col) == 1before the bounds checks throws anArrayIndexOutOfBoundsExceptionon border cells.
Testing
[[1,1,1,1,0],[1,1,0,1,0],[1,1,0,0,0],[0,0,0,0,0]]givesList(9).[[1,1,0,0,0],[1,1,0,0,0],[0,0,1,0,0],[0,0,0,1,1]]givesList(4, 1, 2).[[1,0,1],[0,1,0],[1,0,1]]givesList(1, 1, 1, 1, 1).[[1,1],[1,1]]givesList(4).[[0,0]]givesList().
