Problem overview
The function sizeOfIslands receives grid, an Array<IntArray> in which 1 is land and 0 is water. An island is a group of land cells connected horizontally or vertically; diagonal neighbours don't connect. The function returns a List<Int> with the size of every island, in any order.
For this grid:
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
there are three islands: a block of 4 cells, a lone cell, and a pair of cells at the bottom right. The sizes are 4, 1 and 2. The solution below reports them in the order it finds them when scanning rows from top to bottom, so it returns [4, 1, 2]. Any order is accepted.
Approach: scan, then flood each island
Scan the grid cell by cell. When you meet a land cell that hasn't been counted, you have found a new island. Then run a depth-first search (DFS) from that cell. The search visits every land cell that is connected to it, counting each one, and turns each visited cell into water. After that, the whole island is gone from the grid, so the scan can't count any of its cells again. The count when the search ends is the island's size.
Turning visited cells into water doubles as the "visited" record, so no separate structure is needed. The cost is that the function modifies the grid it receives: after the call, every cell is 0.
The search on a cell does the same few things each time. If the cell is outside the grid or isn't land, stop. Otherwise count it, turn it into water, and repeat on its four neighbours. Neighbours that are outside the grid or already water are rejected by the first check, so the code doesn't need to test them before the call.
Step by step
- Add a counter property.
noOfCellsis avardeclared in the class and set to 0. Every recursive call adds to the same counter, so it lives on the object, not insidedfs. - Create the result list. An empty
ArrayList<Int>collects the sizes as islands are found. - Loop over the rows with
ifrom 0 untilgrid.size. - Loop over the columns with
jfrom 0 untilgrid[0].size, so the two loops together visit every cell. - Check for land. If
grid[i][j] == 1, this cell belongs to an island that hasn't been counted. Cells in finished islands have been flooded to0, so each island is found only once, at its first cell in scan order. - Reset the counter to 0 before exploring, so it counts only the island about to be explored.
- Call
dfs(grid, i, j), which will turn the whole island into water and add one tonoOfCellsper cell. - Record the size by adding
noOfCellsto the result. - Return the result after both loops finish.
- Write
dfswith the parametersgrid,rowandcoland no return type. It reports through the counter and by changing the grid, and the grid is passed by reference, so the caller sees the changes. - Stop on invalid cells. At the start, if
isValidCellsays no, return at once. - Count the cell with
noOfCells++. - Mark it visited by setting it to 0. Without this, two neighbouring land cells would call each other forever.
- Define the four directions as pairs of row and column changes: up, down, left and right.
- Recurse into each neighbour by looping over the directions and calling
dfson(row + d[0], col + d[1]). - Write
isValidCellreturning aBoolean. - Check bounds first, then the cell. The row must be between 0 and
grid.size - 1, the column between 0 andgrid[0].size - 1, andgrid[row][col]must equal 1, all joined by&&.
The solution in Kotlin
class Solution {
fun isValidCell(grid: Array<IntArray>, row: Int, col: Int): Boolean {
return row >= 0 && row < grid.size &&
col >= 0 && col < grid[0].size &&
grid[row][col] == 1
}
fun dfs(grid: Array<IntArray>, row: Int, col: Int) {
if (!isValidCell(grid, row, col)) {
return
}
noOfCells++
grid[row][col] = 0
val directions = arrayOf(intArrayOf(-1, 0), intArrayOf(1, 0), intArrayOf(0, -1), intArrayOf(0, 1))
for (d in directions) {
dfs(grid, row + d[0], col + d[1])
}
}
var noOfCells = 0
fun sizeOfIslands(grid: Array<IntArray>): List<Int> {
val result = ArrayList<Int>()
for (i in 0 until grid.size) {
for (j in 0 until grid[0].size) {
if (grid[i][j] == 1) {
noOfCells = 0
dfs(grid, i, j)
result.add(noOfCells)
}
}
}
return result
}
}
The Kotlin details worth a closer look:
- Short-circuit
&&and line breaks. A line that ends with&&lets the expression continue on the next line. Because&&stops at the first false operand,grid[row][col]is read only after the bounds are known to be fine; reading it first would throwArrayIndexOutOfBoundsExceptionfor neighbours past the edge. - A property declared between functions.
var noOfCells = 0is a member of the class. The order of members in a class doesn't matter in Kotlin, sodfscan use it even though it is declared below. 0 until grid.sizeexcludes the end, so it covers rows0togrid.size - 1.0..grid.sizewould include one row too many.arrayOf(intArrayOf(...), ...)builds anArray<IntArray>of row and column offsets. Indexing withd[0]andd[1]reads the two parts of each pair.- Arrays are mutable, and passed by reference.
grid[row][col] = 0changes the caller's grid. The function return typeList<Int>is a read-only view of theArrayListthat was built. - Recursion depth. A big island makes a deep chain of calls. A fully land grid of 100 by 100 cells overflowed the default JVM stack in a test, throwing
StackOverflowError, while 60 by 60 worked. Small grids are fine; very large ones need an explicit stack.
Complexity
Time: O(R * C) for a grid of R rows and C columns. The scan visits each cell once. Each land cell is entered by the search once, then turned into water, and every call does a constant amount of work plus four more calls that mostly end at once. In total, there are at most four calls per cell.
Space: O(R * C) in the worst case, for the recursion stack. A grid that is entirely land makes one island whose search can reach a depth of the whole cell count. The result list holds one number per island. No visited array is needed.
Edge cases and common mistakes
- No land. A grid of zeros returns an empty list.
- A single cell.
[[1]]returns[1]. - Diagonals don't connect.
[[1, 0, 1], [0, 1, 0], [1, 0, 1]]has five islands of size 1. The four directions in the code exclude diagonal neighbours. - Forgetting to reset the counter. Without
noOfCells = 0before each search, every size would include all the earlier islands. - Forgetting to mark visited cells. The search would bounce between neighbours until the stack overflows.
- Reading the grid before the bounds check. Neighbours of edge cells lie outside the grid, and indexing them throws an exception.
- Expecting the grid to survive. After the call, the grid is all zeros. If the caller still needs the original, copy it first.
- An empty grid. With no rows, the outer loop never runs and the result is empty.
Testing
- The 4 by 5 grid in the first example (rows
1 1 1 1 0,1 1 0 1 0,1 1 0 0 0,0 0 0 0 0) gives[9]. - The grid in the overview gives
[4, 1, 2]. - A 2 by 2 grid of zeros gives
[]. [[1]]gives[1].[[1, 0, 1], [0, 1, 0], [1, 0, 1]]gives[1, 1, 1, 1, 1].[[1, 1], [1, 0]]gives[3].