Problem overview
The method numIslands receives a grid as an Array[Array[Int]]. A cell holding 1 is land and a cell holding 0 is water. An island is a group of land cells connected horizontally or vertically. The method returns how many islands the grid contains.
In the first example, all the 1s are linked through side-by-side neighbours, so there is one island. In the second, the four 1s in the top-left block form one island, the lone 1 in row 2 forms a second, and the two 1s at the bottom right form a third. The answer is 3. Diagonal contact doesn't connect cells: the lone 1 in row 2 touches the top-left block only at a corner.
Approach: count, then erase the island
Scan the grid cell by cell. The first land cell you meet in an island means a new island. The difficulty is that an island has many cells, and you must not count it once per cell.
The fix is to erase an island as soon as it is counted. When the scan reaches a 1, add one to the result and run a depth-first search (DFS) from that cell. The search visits every land cell connected to it and turns each into 0. When the scan continues, the rest of that island is already water, so it can't be counted again. Each island therefore adds exactly 1, at its first cell in scan order.
The DFS is a recursive method. For one cell it asks whether the cell is land inside the grid. If not, it stops. If so, it turns the cell into water and does the same for the four neighbours: up, down, left and right.
Step by step
The lesson writes the main method first and assumes a helper exists, then writes the helpers.
- Declare
resultwithvar, set to 0. It counts the islands found so far and changes later, so it can't be aval. - Loop over the rows with
for (i <- 0 until grid.length).untilexcludes the upper bound, soicovers exactly the valid row indexes. - Loop over the columns inside it with
0 until grid(0).length. Every row has the same length, so the first row's length is the column count. - Check whether
grid(i)(j) == 1. Scala indexes with parentheses, one pair per dimension. - Increment
resultwith+=inside theif. This is the only place the count changes. A land cell reached here wasn't erased by an earlier search, so it belongs to a new island. - Call
dfs(grid, i, j)to erase the island. After the outer loop, end the method withresult. - Write
dfs. It takes the grid, a row and a column, and returnsUnit, which is Scala's "no useful value". - Stop at invalid cells. If
!isValidCell(grid, row, col),returnright away. Water and off-grid neighbours both end the search in that direction. - Mark the cell as water with
grid(row)(col) = 0before recursing. Without it, two neighbouring cells would keep sending the search back to each other forever. - Describe the four moves as an array of (row change, column change) pairs: up
(-1, 0), down(1, 0), left(0, -1)and right(0, 1). - Recurse on each neighbour: loop over
directionsand calldfsonrow + d(0)andcol + d(1). - Write
isValidCell. It returnsfalseif the position is outside the grid, and otherwise whether the cell equals 1. The bounds are tested first because reading outside an array throws.
The solution in Scala
class Solution {
def isValidCell(grid: Array[Array[Int]], row: Int, col: Int): Boolean = {
if (row < 0 || col < 0 || row >= grid.length || col >= grid(0).length) {
return false
}
grid(row)(col) == 1
}
def dfs(grid: Array[Array[Int]], row: Int, col: Int): Unit = {
if (!isValidCell(grid, row, col)) {
return
}
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))
}
}
def numIslands(grid: Array[Array[Int]]): Int = {
var result = 0
for (i <- 0 until grid.length) {
for (j <- 0 until grid(0).length) {
if (grid(i)(j) == 1) {
result += 1
dfs(grid, i, j)
}
}
}
result
}
}
The Scala details worth knowing:
- Arrays of arrays.
Array[Array[Int]]is an array whose elements are themselves arrays, sogrid(row)(col)first picks a row, then a cell in it. Assigning works the same way:grid(row)(col) = 0is a call to the array'supdatemethod, written as an assignment. - The grid is changed in place. Arrays are mutable objects passed by reference, so
dfsmodifies the caller's grid. AfternumIslandsreturns, every cell is 0, and calling it again on the same grid returns 0. Copy the grid first if you still need it. returninside aUnitmethod. A barereturnleavesdfsearly. InisValidCellthe earlyreturn falseis followed by a last expression,grid(row)(col) == 1, whose value is the result when theifdoesn't fire.- Short-circuit
||. The conditions are evaluated left to right and stop at the first true one, sogrid(row)is never read with a badrow. Put the bounds test after the read and the method throwsArrayIndexOutOfBoundsException. - The ranges.
0 until grid.lengthyields 0 throughgrid.length - 1. Using0 to grid.lengthwould include one index too many and throw. - The directions array is rebuilt on every call. It is small, so it costs little, but it could live outside the method as a field.
Complexity
Let the grid have R rows and C columns.
Time: O(R * C). The scan looks at every cell once. Each land cell is erased by exactly one dfs call that gets past the validity check, and every other call returns immediately. A cell is the target of at most four neighbour calls, so the number of calls is at most a constant times the number of cells.
Space: O(R * C) in the worst case. The only extra memory is the call stack. One snaking island covering the whole grid makes the recursion as deep as the number of cells. A very large all-land grid, hundreds of rows by hundreds of columns, can overflow the stack and end the program; the exact size depends on the stack the JVM is given. An explicit stack or queue instead of recursion avoids that limit.
Edge cases and common mistakes
- All water. A grid of zeros returns 0.
- Empty grid.
Array[Array[Int]]()returns 0, because the outer loop never runs andgrid(0)is never evaluated. - All land.
Array(Array(1, 1), Array(1, 1))is one island and returns 1. - Diagonal cells. A 3 by 3 grid with 1s at the four corners and the centre returns 5, because diagonals don't connect.
- Incrementing inside
dfs. The count would go up once per cell rather than once per island. - Marking the cell after the recursive calls. The search would revisit cells it is still working on and recurse until the stack overflows.
- Using
grid.lengthfor the columns. That's the number of rows. The column count isgrid(0).length, which goes wrong on a grid with different numbers of rows and columns. - Rows of different lengths. The solution assumes a rectangular grid. A shorter later row makes the check on
grid(0).lengthlet an out-of-range column through, and the read throws.
Testing
- The first example grid gives
1. - The second example grid gives
3. - A 3 by 3 grid with 1s at the corners and the centre gives
5. Array(Array(0))gives0.Array(Array(1, 1), Array(1, 1))gives1.
