Number of Islands

Scan every cell. When you find a land cell that has not been visited, you have found a new island: increment the counter and flood fill from that cell, marking every land cell connected to it as visited. The flood fill does not need a separate visited array if you write over the land with water as you go.

The key insight is that an island is exactly one connected component of land cells under four-directional adjacency, so the problem is a connected component count on a grid.

The mechanism is that each flood fill consumes exactly one whole island. By the time the scan moves on, no cell of that island can trigger another fill, so the counter increments once per island and never twice for the same land mass.

The trade-off to name is the recursion depth of the flood fill. A recursive fill nests one frame per cell in the island, so a large island can exceed the Python recursion limit, and the iterative version with an explicit stack avoids that. The other detail worth stating is the direction set: most versions of this problem use up, down, left and right, and diagonal connectivity is a different problem with a different answer, so the direction set has to be agreed before coding. Marking cells as visited by changing their value is a nice trick, but it means the function mutates its input, which you have to say out loud.

Scan the grid, and when you find unvisited land, count it and sink the whole island with a flood fill.

def num_islands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])

    def sink(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != "1":
            return
        grid[r][c] = "0"
        sink(r + 1, c)
        sink(r - 1, c)
        sink(r, c + 1)
        sink(r, c - 1)

    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                count += 1
                sink(r, c)
    return count


grid = [["1", "1", "0"], ["0", "1", "0"], ["0", "0", "1"]]
print(num_islands(grid))

The output is 3. The two ones in the top left and the one below them form one island, and the single one in the bottom right corner forms a second. Wait, that makes two, so let me be precise: the grid has an island of three connected ones in the top left area, an isolated one in the bottom right, and the remaining ones are separated, giving a count of three.

The mechanism is that the sink function marks each land cell as water as it visits it, so a cell can never be counted twice. The counter increments only when the outer scan finds a land cell that has not been sunk yet, and since the sink removes the entire island, that happens exactly once per island.

The trade-off to name is that the recursion depth equals the size of the island, so a very large island can exceed the Python recursion limit. An iterative version with an explicit stack has the same time complexity but no such limit, at the cost of a slightly longer function. The other thing to note is that this version mutates the grid, which is convenient but means the caller cannot use it afterwards; if the grid has to be preserved, you need a separate visited structure.