Problem overview
You get a rectangular grid where every cell is land or water, and you return how many islands it contains. An island is a group of land cells connected horizontally or vertically. Diagonal neighbours don't count as connected, and everything outside the grid counts as water.
In this lesson, numIslands receives the grid as [[Int]], an array of rows, with 1 for land and 0 for water. It returns the count as an Int.
Take the second example, written as the array the function receives:
let grid = [
[1, 1, 0, 0, 0],
[1, 1, 0, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 0, 1, 1]
]
The four 1s in the top-left corner touch each other, so they form one island. The single 1 in the middle is a second island: its only land neighbour is diagonal. The two 1s at the bottom right form a third. The answer is 3.
Approach: count an island, then sink it
Scanning the grid cell by cell finds land easily. The hard part is counting each island once, not once per cell. The trick is to erase an island as soon as you count it:
- Visit every cell in row order.
- When a cell is land, it must belong to an island you haven't seen yet, so add 1 to the count.
- Immediately turn that cell and every land cell connected to it into water. This is a flood fill, done here with depth-first search (DFS).
After step 3, no later cell of the same island is still land, so the scan can't count it again. On the example, the scan counts the island at (0, 0) and sinks all four of its cells. Cells (0, 1), (1, 0) and (1, 1) are water by the time the scan reaches them. The scan then finds (2, 2), counts it and sinks it, and finally counts (3, 3), sinking it together with (3, 4).
The DFS is naturally recursive: to sink a cell, mark it as water and then try to sink each of its four neighbours. A neighbour that is off the grid or already water stops that branch. Breadth-first search with a queue, or a union-find structure, would also work with the same running time. DFS needs the least code.
Step by step
- A mutable copy and a counter. The starter code copies the grid into a
var, because the search will change it. Next to it goesresult, starting at 0. - Two nested loops walk every row index
iand every column indexj. The number of columns comes from the first row, since all rows have the same length. - A land check. Only a cell that is still 1 starts a new island. Water, including land that an earlier search has sunk, is skipped.
- Count, then sink. Increase
resultonce and calldfson the cell. The count changes in exactly one place, so each island adds exactly 1. - Return the count after both loops finish.
- The
dfshelper takes the grid as aninoutparameter so its changes reach the caller's copy, plus the row and column of the cell to sink. - A stopping rule first. If the cell is off the grid or not land, return at once. This single check ends every branch of the search.
- Mark before recursing. Set the cell to 0 before visiting any neighbour. If two neighbouring cells were both still land while their searches ran, each would call the other forever.
- Spread to the four neighbours. A list of row and column offsets describes up, down, left and right, and the helper calls itself once per offset.
- The
isValidCellhelper checks the bounds before reading the cell, and only then checks whether the cell is land.
The solution in Swift
class Solution {
func isValidCell(_ grid: [[Int]], _ row: Int, _ col: Int) -> Bool {
if row < 0 || col < 0 || row >= grid.count || col >= grid[0].count {
return false
}
return grid[row][col] == 1
}
func dfs(_ grid: inout [[Int]], _ row: Int, _ col: Int) {
if !isValidCell(grid, row, col) {
return
}
grid[row][col] = 0
let directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
for d in directions {
dfs(&grid, row + d[0], col + d[1])
}
}
func numIslands(_ grid: [[Int]]) -> Int {
var grid = grid
var result = 0
for i in 0..<grid.count {
for j in 0..<grid[0].count {
if grid[i][j] == 1 {
result += 1
dfs(&grid, i, j)
}
}
}
return result
}
}
Several Swift features carry this solution:
- Parameters are constants.
gridinsidenumIslandscan't be modified, sovar grid = griddeclares a mutable local copy with the same name. Swift arrays are value types with copy-on-write: the copy shares storage with the caller's array until the first write, and the caller's grid is never changed. inoutand&. Withoutinout,dfswould receive its own constant copy and couldn't sink anything. With it, the function's changes are written back to the caller's variable. Swift makes this visible at every call site: passing an argument to aninoutparameter requires&, and leaving it out is a compile error.isValidCellonly reads the grid, so it takes a plain parameter.- Unlabelled arguments. The
_before each parameter name removes the argument label, which is why the calls readdfs(&grid, i, j)rather thandfs(grid: &grid, row: i, col: j). - Half-open ranges.
0..<grid.countincludes 0 and stops beforegrid.count, exactly the valid indices. For an empty grid it is the empty range0..<0, so the outer loop never runs andgrid[0]is never touched. - Indexing out of range crashes. Swift checks every array index at run time and stops the program on a bad one.
isValidCellrelies on||short-circuiting: the comparisons are evaluated left to right, andgrid[row][col]is read only after all four bounds tests pass.
Complexity
Let R be the number of rows and C the number of columns.
Time: O(R · C). The nested loops look at each cell once. Each land cell is sunk exactly once, because it becomes water the moment it is visited, and sinking it makes four more calls. Every other call returns immediately. That is a constant amount of work per cell.
Space: O(R · C) in the worst case. The local copy of the grid can take up to R · C cells once the search modifies it. The recursion also uses stack space: on a grid that is all land, the search can wind through every cell before it backtracks, so the depth can reach R · C.
Edge cases and common mistakes
- No land. A grid of only 0s returns 0, and so does an empty grid.
- Diagonal cells.
[[1, 0], [0, 1]]has two islands, not one. Adding diagonal moves todirectionswould merge them. - Marking too late. If the cell is set to 0 after the recursive calls instead of before, two neighbouring land cells keep calling each other until the program runs out of stack.
- Reading before checking bounds. Testing
grid[row][col] == 1first crashes as soon as the search steps off an edge. - Counting inside
dfs. That counts land cells, not islands. The count belongs in the scan, right before the call. - Mixing up rows and columns. Rows run up to
grid.countand columns up togrid[0].count. Swapping them works on square grids and fails on every other shape. - Very large islands. The recursion depth grows with the island's size. If deep recursion is a concern, the same flood fill can be written with an explicit stack or queue.
Testing
[[1]]returns 1.[[0]]returns 0.[[1, 0], [0, 1]]returns 2 (diagonals are separate).[[1, 0, 1, 0, 1]]returns 3 (a single row).[[1], [0], [1], [1]]returns 2 (a single column).[[1, 1, 1], [0, 1, 0], [1, 1, 1]]returns 1 (connected through the middle).
