Count connected islands in a rectangular grid where # is land and ~ is water. Land cells connect only through shared sides, not diagonally. The selected solution changes visited land to water in its working map. Reference-based versions consume the caller's map; a version that explicitly copies it preserves the original. For [['#', '~'], ['~', '#']], return two, because the two land cells touch only at a corner.
Start one flood fill per unseen island
Scan every cell in row order. Water needs no action. When the scan finds land, increment the island count and flood-fill all land connected to that cell. The flood fill changes each reached land cell to water, preventing a later scan position from counting the same island again.
The fill recursively explores the four side neighbors. It stops when coordinates leave the grid or the current cell is water. Mark the current cell before exploring neighbors. Otherwise two adjacent land cells can recurse into each other indefinitely, since neither has yet recorded that it was visited.
Trace a connected shape
Consider [['#', '#', '~'], ['~', '#', '~'], ['#', '~', '#']]. The scan starts an island at the upper-left cell. Its flood fill reaches the upper-middle and center cells, marking all three as water. Later visits to those positions do nothing. The lower-left cell starts a second island, and the lower-right cell starts a third.
A diagonal move from the center to the lower-left or lower-right would incorrectly join those islands. The neighborhood definition is part of the problem, not a traversal detail. A map using eight-way connectivity requires a different neighbor list and would produce a different result on this example.
Prove that each component is counted once
When a scan encounters remaining land, that land belongs to a component no earlier flood fill has reached. Incrementing the count therefore adds a previously uncounted island. The flood fill follows every path of side-adjacent land in that component, marking it all before the outer scan continues.
No cell in that component can trigger a later increment because all of it is now water. Conversely, any island has a first cell reached by the scan, and that cell triggers its count unless an earlier cell in the same island already did. Thus every connected component contributes exactly one increment.
Include mutation and recursive storage
Each cell is examined by the scan, and each land cell initiates at most four recursive neighbor calls before becoming water. Total time is O(r × c). Recursive depth can also reach O(r × c) on a long connected shape. Calling the algorithm constant-space because it has no visited array ignores those call frames.
Python and other runtimes can exhaust the call stack on a large connected island. An explicit stack avoids recursive frames but still needs storage for pending cells. To preserve the input, copy every row before flooding or keep a separate visited structure. Copying only the outer collection can leave inner rows shared in reference-based languages.
Test both count and side effects
Use all water, all land, one cell, one row, one column, a ring around a water hole, and diagonally separated cells. A long narrow island checks traversal depth. All land in the working map should be water afterward. Where the caller's map is changed, running the function again on that same map should return zero. A copied-input version should return the original count again.
For an independent count oracle, treat each land cell as a vertex and join only right and down land neighbors with a disjoint-set structure. The number of resulting components should equal the flood-fill count. A follow-up can ask for the largest island area: the fill must then accumulate the number of cells it marks rather than only recording that a component exists.
Swift implementation
This version copies grid into a local map and marks that value through inout. The caller’s grid remains unchanged; copying adds grid storage.
The course uses the class shown here and supplies any declared node classes. Swift arrays have value semantics with copy-on-write storage, while class instances such as linked nodes retain reference identity. Optional values require an explicit absence case. Keep the starter's argument labels when calling the method. Swift integer overflow traps, so expanded constraints require a checked arithmetic policy.
class Solution {
private let land: Character = "#"
private let water: Character = "~"
func countIslands(_ grid: [[Character]]) -> Int {
if grid.isEmpty || grid[0].isEmpty {
return 0
}
// Arrays are values in Swift, so we mark a copy of the map
var map = grid
let numRows = map.count
let numCols = map[0].count
var islandCount = 0
for row in 0..<numRows {
for col in 0..<numCols {
// We found another uncounted island
if map[row][col] == land {
islandCount = islandCount + 1
// Mark all the pieces of land for the island as viewed
markLandAsViewedDFS(&map, row, col)
}
}
}
return islandCount
}
private func markLandAsViewedDFS(_ map: inout [[Character]], _ row: Int, _ col: Int) {
let numRows = map.count
let numCols = map[0].count
// Stopping condition:
// 1. Outside of the map
// 2. Reached an adjacent water node
let isOutsideMap = row < 0 || col < 0 || row >= numRows || col >= numCols
if isOutsideMap || map[row][col] == water {
return
}
// Recursive case:
// 1. Mark the node as viewed by flipping it to water
// 2. Check the nodes adjacent to the current
map[row][col] = water
markLandAsViewedDFS(&map, row - 1, col)
markLandAsViewedDFS(&map, row + 1, col)
markLandAsViewedDFS(&map, row, col - 1)
markLandAsViewedDFS(&map, row, col + 1)
}
}
Practice this implementation
Open Count Islands to run the implementation against the course tests, then change one boundary condition and explain the first failing case. The editor supplies the starter signature and any node types or helper APIs used above. Copy the implementation into that environment; the snippet is the solution body, without the input parser or test driver. Your saved progress belongs to the original lesson.
For more Swift conventions and practice problems, use the Swift interview guide.