Number of Islands: Flood Fill, Input Mutation, and Connectivity Rules

Number of Islands is a connected-component problem with two contracts you should state before writing code: which cells count as neighbors, and whether the solution may modify the input. For the standard four-neighbor version, scan the grid and start one flood fill whenever you find undiscovered land. Mark land when you discover it so another path cannot schedule it again.

Practice both traversal orders with PracHub’s Implement island counting with BFS and DFS. The original implementation below includes preserving and destructive modes, an explicit correctness argument, and executed local checks. These are preparation exercises, not evidence of an employer’s current interview format or hidden tests.

Read the connectivity and representation contract

Official problem contract: LeetCode’s Number of Islands describes string cells representing land and water, with land connected horizontally or vertically. Diagonal contact therefore does not join components. If your interviewer changes adjacency to eight neighbors, that is a different graph even though the input looks identical.

Use this adversarial grid:

1 0 1
0 1 0
1 0 1

Under four-neighbor connectivity, the answer is five. Under eight-neighbor connectivity, the center touches all four corners diagonally and the answer is one. In the original local fixture, both counts were checked against a disjoint-set reference. This tiny example catches a wrong neighbor list more directly than a large random grid.

Clarify whether cells are strings or integers. The implementation here deliberately accepts only string zero and one. Mixing a string comparison with integer input can return zero without traversing any land. Also confirm rectangular shape, empty-grid behavior, and whether boundary land counts. Standard island counting includes land touching the edge; “closed islands” adds a separate requirement.

The code expects independent mutable row lists when destructive mode is enabled. Aliased rows, such as a matrix made by repeating the same inner list, violate that representation contract. Validate rectangular shape and cell values before mutating so a malformed later row does not leave earlier rows half-consumed.

Count roots of searches, not cells

An outer scan visits each coordinate. Water is skipped. Land already reached by an earlier flood fill is also skipped. When the scan finds undiscovered land, increment the island count once, then discover its entire connected component.

Increment the answer once for each previously undiscovered land root. It should not increase for each neighbor, queue entry, boundary crossing or recursive return. Those events describe traversal mechanics, while the answer counts components.

Maintain this invariant: every discovered land cell belongs to a component whose count has already been added, and each discovered cell is scheduled for processing at most once. Mark the initial root before pushing it. For every eligible neighbor, mark first and then push. The stack or queue contains discovered work, not a set of still-unclaimed candidates.

To justify completeness, take any land cell connected to a search root. Along a path from the root, the first not-yet-discovered cell has a discovered predecessor that will inspect their edge, so that cell will be discovered too. To justify separation, the traversal crosses only land edges permitted by the neighbor rule. It cannot consume a different component.

After one component is consumed, the next undiscovered land root must belong to another component. Together these arguments explain why one count per root produces the number of islands. The proof is reasoning about the algorithm; the finite tests later provide a separate implementation check.

Implement iterative DFS with an explicit mutation choice

Here is the complete function executed in the local fixture. Preserving mode copies each row; destructive mode uses the supplied grid directly. Changing discovered land to water acts as the visited marker.

def count_islands(grid, *, in_place=False):
    if not grid:
        return 0
    cols = len(grid[0])
    if any(len(row) != cols for row in grid):
        raise ValueError('rectangular grid required')
    if any(cell not in ('0', '1') for row in grid for cell in row):
        raise ValueError('string binary cells required')
    board = grid if in_place else [row[:] for row in grid]
    rows = len(board)
    count = 0
    for r in range(rows):
        for c in range(cols):
            if board[r][c] != '1':
                continue
            count += 1
            board[r][c] = '0'
            stack = [(r, c)]
            while stack:
                x, y = stack.pop()
                for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    nx, ny = x + dx, y + dy
                    if (0 <= nx < rows and 0 <= ny < cols
                            and board[nx][ny] == '1'):
                        board[nx][ny] = '0'
                        stack.append((nx, ny))
    return count

For an empty outer list or a rectangular zero-width grid, the function returns zero. A nonrectangular grid or a cell outside the string-binary contract raises ValueError before changes occur. These validation choices make this teaching function’s behavior explicit; match the actual interview contract rather than adding every possible validation layer by habit.

The default preserves the caller’s grid. An outer copy such as grid[:] is insufficient because it still references the original row lists. Copying every row separates the mutable cells in this representation. If cells were themselves mutable objects, you would need to reconsider the copying contract rather than assuming a row copy is universally deep.

After a destructive call, every original land cell has become water. Running the same function on that same grid again returns zero. If your BFS test reuses the grid already consumed by DFS, it can return zero for the wrong reason; give each destructive test its own rows.

Mark on discovery to control duplicate work

Consider a two-by-two block of land. From the upper-left root, both the cell to its right and the cell below it lead to the lower-right cell. If that cell stays unmarked until removal from the frontier, both paths can add it.

Marking at insertion prevents the duplicate. Our queue-based fixture recorded exactly four insertions for the four-cell block. If you mark on removal instead, a guard can still skip repeated entries, but your scheduling invariant and work accounting change. Do not claim every cell enters the frontier once unless your code actually enforces it.

Check both bounds before indexing a Python row or column. A negative row or column index can access the opposite end of a list rather than failing. Check both lower and upper bounds before reading the cell. A missing lower-bound check can accidentally connect the top and bottom or the left and right edges.

Compare DFS, BFS and union-find on the right workload

Iterative DFS uses a stack and explores a path before returning to other pending branches. BFS uses a queue and processes discoveries in layers. For static component counting, their exploration order changes but the component definition and root-count rule do not.

Python’s collections documentation provides deque with efficient operations at both ends. Use popleft for queue removal. Use a list’s end for stack operations; use deque for BFS so removing the next cell does not shift the remaining frontier. The outer algorithm can be correct while that queue choice adds avoidable work.

Recursive DFS is concise, but a component can contain a long path. Python documents an interpreter recursion limit intended to protect its stack, and increasing it too far can be unsafe. This implementation stores pending cells in a list rather than recursing once per path step. Our fixture handled a single row of 20,000 land cells; this is a functional observation, not a timing benchmark or a measured recursion-failure threshold.

For an m-by-n grid, scanning and traversing four neighbors per land cell gives O(mn) time. Each land cell is marked once and scheduled once. The validation pass and optional row copy are also linear, so they do not change that bound.

Count the copied board and the pending stack separately when explaining extra memory. Preserving mode copies O(mn) cells. Destructive mode avoids that copy, but the pending frontier can still require O(mn) storage in the worst case. A recursive implementation has its own stack cost. Explain whether your space statement excludes the input, and include every structure your chosen version allocates.

Recognize when an additions follow-up changes the problem

If land arrives one cell at a time and the interviewer wants a count after every addition, repeatedly flooding the whole grid can be wasteful. A disjoint-set structure tracks active land components. A genuinely new land cell initially adds one component; each successful union with a distinct neighboring component reduces the count by one.

Repeated additions must be idempotent. A neighbor in the same component must not reduce the count again. For example, adding a cell beside two neighbors that are already connected creates only one merge with their component. Comparing roots before union is essential to the count update.

This is a proposed follow-up, not an incremental implementation included in our fixture. The union-find interview guide develops representative tracking and its limits. Deleting land can split a component; ordinary union-find does not provide that operation just because it supports additions efficiently.

Static counting, maximum area, perimeter and shortest bridge also need different outputs. Count roots for the first, accumulate component size for area, inspect exposed edges for perimeter, and reason about distance for a bridge. Avoid carrying a memorized count increment into a variant whose answer measures something else.

Use adversarial tests to explain your choices

The original Python 3.12.14 fixture checked all 682 binary grids with one to three rows and one to three columns. For each grid, iterative DFS matched an independent disjoint-set reference, preserving mode left the input unchanged, BFS insertion count equaled the number of land cells, and destructive mode consumed every land cell. A second destructive call returned zero.

Additional cases checked the diagonal grid, empty inputs, malformed shape, nonbinary values, the four-cell cycle and the long row. The complete run executed 2,736 assertions. Exhaustive coverage of those small shapes does not prove arbitrary-grid correctness; that is why the discovery and component arguments accompany the code.

During an interview, explain what each small test rules out. The diagonal grid catches an adjacency mismatch. A singleton on the boundary catches an accidental closed-island rule. The cycle catches repeated discovery. Running two implementations on independent copies catches a test harness that hides mutation.

Then state the assumption that would change your approach: preserving immutable input, processing a huge connected component, returning distances, or answering after many additions. Choose the data structure after naming that contract change, then check the same connectivity invariant under the revised operations.

Rehearse five related grid prompts

These PracHub records span reported software-engineering and data-engineering practice. They support separate exercises, not a single employer’s scoring rubric. Read each representation and mutation rule before reusing the function.

Start with BFS without modifying the grid, then explain how its visited set corresponds to the destructive marker in the DFS above. Check both on the diagonal grid and a connected cycle before moving to dynamic additions.

Sources and Further Reading

• LeetCode: Number of Islands problem contract
• Python: deque operations
• Python: recursion limit and stack cautions
• Python: lists as stacks and queues