Problem overview
The method sizeOfIslands receives grid, a two-dimensional array of integers where 1 is land and 0 is water. An island is a group of land cells connected horizontally or vertically. The method returns an array with the size of every island, in any order. The edges of the grid can be treated as surrounded by water.
In the first example, all nine land cells are linked through side-by-side neighbours, so the result is [9]. In the second, the top-left 2x2 block has 4 cells, the lone cell in row 2 has 1, and the two cells at the bottom right have 2. The result holds 1, 4 and 2 in some order. The lone cell touches the block only at a corner, and diagonal contact does not connect cells.
Approach: scan, then flood one island at a time
Scan the grid cell by cell. When the scan meets a land cell that has not been used yet, it has found a new island. Run a depth-first search (DFS) from that cell. The search visits every land cell connected to it, counts them, and turns each one into water so that nothing is counted twice and the scan skips the island afterwards. When the search returns, the count is the island's size, and it goes into the result.
The counter lives in a property of the class, noOfCells. Every recursive call adds to the same counter, so it can't be a local variable of the search function. The scan sets it to 0 before each search.
On the second example, the scan meets the cell at row 0, column 0 first. The search counts 4 cells and erases them. The scan reaches the lone cell at row 2 next, which counts 1, and finally the pair at the bottom right, which counts 2. The result is [4, 1, 2], which is the same set of sizes in a different order.
Step by step
- Declare the property
noOfCellsin the class, avarstarting at 0. It counts the cells of the island being explored. - Copy the grid and create
result. Parameters are constants in Swift, sovar grid = gridmakes a mutable local copy.resultstarts as an empty[Int]. - Loop over the rows with
iin0..<grid.count. - Loop over the columns with
jin0..<grid[0].count, the length of a row. - Test for land. If
grid[i][j] == 1, the cell belongs to an island that no search has erased yet. - Reset
noOfCellsto 0. The counter should hold only the island about to be explored. - Call
dfs(&grid, i, j). The ampersand passes the grid as aninoutargument, so the search can change it. - Append
noOfCellstoresult. After the search returns, it holds the island's size. - Return
resultafter both loops. - Write
dfswith aninoutgrid, a row and a column, and no return value. - Stop at invalid cells. If
isValidCellsays the cell is off the grid or water,returnat once. - Count the cell with
noOfCells += 1. - Erase the cell by setting it to 0. Without this, neighbouring cells would send the search back and forth forever.
- Declare
directionsas four tuples: up(-1, 0), down(1, 0), left(0, -1), right(0, 1). - Recurse on each neighbour by adding the offsets to the row and column. Neighbours that are outside the grid or in the water are rejected by the check at the top.
- Write
isValidCellto return one condition: the row and column are inside the grid and the cell equals 1. The bounds come first so that an out-of-range index is never read.
The solution in Swift
class Solution {
func isValidCell(_ grid: [[Int]], _ row: Int, _ col: Int) -> Bool {
return row >= 0 && row < grid.count &&
col >= 0 && col < grid[0].count &&
grid[row][col] == 1
}
func dfs(_ grid: inout [[Int]], _ row: Int, _ col: Int) {
if !isValidCell(grid, row, col) {
return
}
noOfCells += 1
grid[row][col] = 0
let directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
for (i, j) in directions {
dfs(&grid, row + i, col + j)
}
}
var noOfCells = 0
func sizeOfIslands(_ grid: [[Int]]) -> [Int] {
var grid = grid
var result = [Int]()
for i in 0..<grid.count {
for j in 0..<grid[0].count {
if grid[i][j] == 1 {
noOfCells = 0
dfs(&grid, i, j)
result.append(noOfCells)
}
}
}
return result
}
}
The Swift details worth a closer look:
- The caller's grid is safe. Arrays are value types, so
var grid = gridmakes a logical copy. Erasing cells changes only the copy. AftersizeOfIslands([[1, 1], [1, 1]])returns[4], the array passed in still holds all ones. The copy is made lazily, when the first cell is written. inout. A parameter markedinoutis written back to the caller's variable when the function returns, and the call site marks it with&. The sameinoutgrid is passed down through every recursive call.- A stored property used as a counter.
noOfCellsbelongs to theSolutionobject, so all the methods share it. It also keeps its last value after the method returns. That is harmless here, because it is reset before every search, but it means the object remembers state between calls. - Declaration order. In a class, a method may use a property or another method declared further down. The order in the file doesn't matter.
- Tuple destructuring.
for (i, j) in directionsunpacks each tuple into two constants. Insidedfs,iandjare offsets, not loop indices. - Short-circuit evaluation. In
isValidCell,&&stops at the first false operand. Because the bounds tests come first,grid[row][col]is read only for valid positions.
Complexity
Let the grid have R rows and C columns.
Time: O(R * C). The scan visits each cell once. Each land cell is erased by exactly one dfs call that passes the check, and the calls that fail it return at once. Every cell is the neighbour of at most four others, so the total number of calls stays within a constant times the number of cells. The copy of the grid costs O(R * C) too.
Space: O(R * C). The copy of the grid takes that much room. The recursion can also go as deep as the largest island, which could cover the whole grid.
Edge cases and common mistakes
- All water. A grid of zeros returns
[], because no search ever starts. - One big island.
[[1, 1], [1, 1]]returns[4]. - Diagonal cells.
[[1, 0, 1], [0, 1, 0], [1, 0, 1]]returns five islands of size 1, so[1, 1, 1, 1, 1]. - A single row.
[[1, 0, 1]]returns[1, 1]. - An empty grid.
[]returns[], since the outer loop runs zero times. ButisValidCellreadsgrid[0], so a grid with rows is assumed to have at least one column in each row. - Forgetting to reset
noOfCells. Each island's size would include all the previous islands. - Erasing after the recursive calls. The search would revisit cells it is still working on, so it would never finish.
- Passing the grid without
&. Swift reports a compile error: aninoutargument must be marked with the ampersand.
Testing
[[1,1,1,1,0],[1,1,0,1,0],[1,1,0,0,0],[0,0,0,0,0]]gives[9].[[1,1,0,0,0],[1,1,0,0,0],[0,0,1,0,0],[0,0,0,1,1]]gives sizes 4, 1 and 2, in the order[4, 1, 2].[[0,0],[0,0]]gives[].[[1,0,1],[0,1,0],[1,0,1]]gives[1, 1, 1, 1, 1].
