Implement island counting with BFS and DFS

Question

You are given an m x n grid of characters where '1' represents land and '0' represents water. Count the number of distinct islands (connected land regions). Two land cells belong to the same island if they share a side — up, down, left, or right. Cells that touch only at a corner (diagonally) are not connected and count as separate islands.

For example, the grid below contains 3 islands:

1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

1. Primary solution. Implement countIslands(grid) using any approach you like, running in O(m·n) time. Explain why it is correct and analyze its time and space complexity.
2. Explicit BFS version. Re-implement the count using an explicit breadth-first search (an iterative queue, no recursion). State its time and space complexity and compare the trade-offs against your first solution.
3. Edge cases. Make sure the solution behaves correctly on: an empty grid (null / 0 rows / 0 columns), an all-water grid, a single-cell grid, a grid that is entirely land, and very large grids. Confirm that diagonally-touching land cells are treated as separate islands.
4. Testing. Describe (or write) tests that validate the solution on several nontrivial cases, including the examples above.
5. Follow-up. Briefly describe how your solution would change if diagonal (8-directional) adjacency also counted as connected.

Part 1: Count Islands in a Grid Using Any O(m*n) Approach

You are given an m x n grid where each cell is either '1' for land or '0' for water. Count how many distinct islands exist in the grid. An island is a maximal group of land cells connected horizontally or vertically. Diagonal contact does not connect islands. Your algorithm should run in O(m*n) time and should handle empty grids.

Constraints

• grid may be None.
• 0 <= m <= 1000
• 0 <= n <= 1000
• If m > 0 and n > 0, grid is rectangular.
• Each cell is either '0' or '1'.
• The intended time complexity is O(m*n).

Examples

Example 1

Input: ([['1','1','0','0','0'],['1','1','0','0','0'],['0','0','1','0','0'],['0','0','0','1','1']],)
Output: 3

Explanation: The top-left block, the middle cell, and the bottom-right pair are three separate 4-directional islands.

Example 2

Input: ([],)
Output: 0

Explanation: An empty grid contains no land.

Hints

1. Scan every cell. When you find unvisited land, you have discovered a new island.
2. After discovering an island, traverse from that cell to mark every land cell in the same connected component.

Part 2: Count Islands Using Explicit Iterative BFS

You are given an m x n grid where '1' represents land and '0' represents water. Count the number of distinct islands, where land cells are connected only by sharing an edge: up, down, left, or right. Implement the traversal using an explicit breadth-first search queue. Recursion is not allowed.

Constraints

• grid may be None.
• 0 <= m <= 1000
• 0 <= n <= 1000
• If m > 0 and n > 0, grid is rectangular.
• Each cell is either '0' or '1'.
• Use an iterative queue-based BFS, not recursion.

Examples

Example 1

Input: ([['1','1','0','0','0'],['1','1','0','0','0'],['0','0','1','0','0'],['0','0','0','1','1']],)
Output: 3

Explanation: There are three 4-directionally connected land components.

Example 2

Input: ([[]],)
Output: 0

Explanation: A grid with zero columns contains no cells and therefore no islands.

Hints

1. A queue processes cells layer by layer, but for counting islands, the important part is that it eventually visits the whole connected component.
2. Mark a land cell as visited when it is enqueued, not when it is dequeued, to avoid adding it multiple times.

Part 3: Count Islands with 8-Directional Diagonal Adjacency

You are given an m x n grid where '1' represents land and '0' represents water. Count the number of distinct islands when land cells are connected if they share either a side or a corner. In other words, use 8-directional adjacency: horizontal, vertical, and diagonal neighbors all count as connected.

Constraints

• grid may be None.
• 0 <= m <= 1000
• 0 <= n <= 1000
• If m > 0 and n > 0, grid is rectangular.
• Each cell is either '0' or '1'.
• The intended time complexity is O(m*n).

Examples

Example 1

Input: ([['1','1','0','0','0'],['1','1','0','0','0'],['0','0','1','0','0'],['0','0','0','1','1']],)
Output: 1

Explanation: With diagonal adjacency, the top-left block connects diagonally to the middle cell, which connects diagonally to the bottom-right land.

Example 2

Input: (None,)
Output: 0

Explanation: A null grid contains no islands.

Hints

1. The overall connected-component strategy is the same as 4-directional island counting.
2. The key change is the neighbor list: include all eight offsets around a cell.

Solution

Rubric: the candidate should recognize this as counting connected components on an implicit grid-graph and produce a clean O(m·n) flood-fill that sweeps every cell once, increments the count on each newly-discovered component, and sinks (marks visited) the rest of that component. Strong answers deliver BOTH a recursive DFS and a correct explicit-queue BFS, articulate the trade-off (DFS stack is O(m·n) and can overflow on a huge all-land grid; BFS frontier is O(min(m,n)) with no stack risk), and mark cells visited on enqueue in the BFS. They handle the empty/all-water/single-cell/all-land/large edge cases, treat diagonal-only contact as separate islands under four-directional rules, and for the follow-up change only the neighbor set to 8 directions (no other change, same complexity). Bonus signal: a union-find alternative, in-place mutation vs. visited-matrix trade-off, and a concrete test plan.

This is the classic "Number of Islands" connected-components problem on a grid. The grid is an implicit graph: each '1' cell is a node, and edges connect orthogonally-adjacent land cells. The number of islands is the number of connected components among the land cells. We sweep every cell once; when we hit an unvisited land cell we have found a new island, so we increment the counter and "sink" (mark visited) the entire component before moving on. Whether we flood the component with DFS, BFS, or union-find, every land cell is visited a constant number of times, giving O(m·n) total work.

1) Primary solution (recursive DFS / flood fill)

Iterate over every cell. The first time we touch a land cell that hasn't been visited, increment the island count and run a DFS that marks the whole connected region as visited (we mutate '1' → '0' in place to avoid a separate visited set; use a visited matrix instead if the input must be preserved).

def count_islands(grid):
    if not grid or not grid[0]:
        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'  # mark visited
        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

Correctness: each land cell is reachable from exactly one "seed" cell — the first cell of its component encountered in row-major order. We increment the counter exactly once per seed and then flood-fill the rest of that component, so it is never counted again. Cells reachable only diagonally are never visited by the four orthogonal recursive calls, so corner-touching regions are correctly counted separately.

Complexity: O(m·n) time — every cell is visited a constant number of times. Space is O(m·n) in the worst case for the recursion stack (a grid that is entirely land degenerates into a single deep recursion). If grid may not be mutated, add an O(m·n) visited matrix.

2) Explicit BFS version (iterative queue, no recursion)

Same outer sweep, but flood each component with an explicit FIFO queue instead of recursion. This avoids the call-stack depth that can overflow on very large all-land grids.

from collections import deque

def count_islands_bfs(grid):
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[0])
    DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))
    count = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != '1':
                continue
            count += 1
            grid[r][c] = '0'           # mark on enqueue, not dequeue
            q = deque([(r, c)])
            while q:
                cr, cc = q.popleft()
                for dr, dc in DIRS:
                    nr, nc = cr + dr, cc + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                        grid[nr][nc] = '0'  # mark as visited when enqueued
                        q.append((nr, nc))
    return count

Key detail: mark a cell visited the moment you enqueue it (not when you dequeue it). Marking on dequeue lets the same cell be added to the queue from multiple neighbors before it is processed, which is a common bug that breaks complexity and can double-process cells.

Complexity: O(m·n) time — each cell is enqueued and dequeued at most once. Space is O(min(m, n)) in the typical analysis for the queue (the BFS frontier), versus the DFS version's O(m·n) recursion stack. The BFS version trades a little extra bookkeeping for bounded, predictable memory and no stack-overflow risk on huge inputs — which is exactly why an interviewer asks for it explicitly.

3) Edge cases

• Empty grid (grid is None, 0 rows, or 0 columns): the guard if not grid or not grid[0] returns 0.
• All-water grid: the outer loop never finds a '1', so the count stays 0.
• Single-cell grid: [['1']] → 1; [['0']] → 0.
• All-land grid: one island. This is the worst case for the recursive DFS stack — prefer the BFS (or an explicit stack) here to avoid overflow.
• Very large grids: the algorithm is linear in the number of cells; the practical risk is recursion depth, which the iterative BFS avoids.
• Diagonal-only contact: with four-directional moves, two regions touching only at a corner are never merged and are counted as separate islands, as required.

4) Testing

Validate on several cases (and re-run with a fresh copy of the grid for each, since the in-place versions mutate it):

assert count_islands([]) == 0
assert count_islands([['0','0'],['0','0']]) == 0
assert count_islands([['1']]) == 1
assert count_islands([['1','1','1'],['1','1','1']]) == 1
# diagonal touch -> separate islands
assert count_islands([['1','0'],['0','1']]) == 2
assert count_islands([
    ['1','1','0','0','0'],
    ['1','1','0','0','0'],
    ['0','0','1','0','0'],
    ['0','0','0','1','1'],
]) == 3

Run the same assertions against count_islands_bfs to confirm both implementations agree. Good additional cases: a checkerboard (maximizes island count), a single long snake of land, and a large random grid compared against a reference union-find implementation.

5) Follow-up: diagonal (8-directional) adjacency

The only change is the neighbor set: extend the direction list from the 4 orthogonal moves to all 8 (add the four diagonals (±1, ±1)). Nothing else changes — same outer sweep, same flood-fill, same O(m·n) complexity. With 8-directional connectivity, corner-touching cells now merge into one island, so the grid in case 3 above ([['1','0'],['0','1']]) would report 1 instead of 2.

Common pitfalls

• Forgetting the empty / null grid guard before reading grid[0].
• In BFS, marking cells visited on dequeue instead of on enqueue (lets cells be queued multiple times).
• Recursive DFS stack overflow on a very large all-land grid — the reason the explicit BFS/iterative version is requested.
• Accidentally treating diagonal contact as connected when only four-directional adjacency is specified.
• Reusing the same mutated grid across both implementations or across tests without resetting it.