# The Island Counter

> Surrounded by water, connected by land - how many separate landmasses?

Canonical URL: <https://datadriven.io/problems/the_island_counter>

Domain: Python · Difficulty: medium · Seniority: L4

## Problem

Given a 2D grid of '1' (land) and '0' (water) strings, return the number of distinct islands (connected groups of land cells using 4-directional adjacency).

## Worked solution and explanation

### Why this problem exists in real interviews

This tests **graph traversal on a grid** using DFS or BFS to identify connected components. It is one of the most commonly asked medium-difficulty problems and probes recursive thinking and grid boundary handling.

---

### Break down the requirements

#### Step 1: Scan the grid for unvisited land cells

Each unvisited `'1'` is the start of a new island.

#### Step 2: DFS/BFS to mark all connected land

From each starting cell, traverse all horizontally and vertically connected `'1'` cells and mark them as visited.

#### Step 3: Count the number of traversals

Each DFS/BFS invocation from the outer loop represents one island.

---

### The solution

**DFS flood-fill for connected components**

```python
def count_islands(grid: list) -> int:
    if not grid:
        return 0
    rows = len(grid)
    cols = len(grid[0])
    count = 0
    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if grid[r][c] != '1':
            return
        grid[r][c] = '0'
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)
    return count
```

> **Time and Space Complexity**
>
> **Time:** O(m * n) where m and n are the grid dimensions. Each cell is visited at most once.
> 
> **Space:** O(m * n) for the recursion stack in the worst case (a grid entirely filled with land).

> **Interviewers Watch For**
>
> Whether you mark cells as visited during traversal. Without marking, infinite loops occur in the DFS.

> **Common Pitfall**
>
> Including diagonal neighbors. The problem specifies horizontal and vertical adjacency only.

---

## Common follow-up questions

- What if you cannot modify the input grid? _(Tests using a separate visited set or matrix.)_
- How would you find the largest island? _(Tests tracking the size of each DFS traversal.)_
- What if the grid is very large and recursion depth is a concern? _(Tests iterative BFS with a queue instead of recursive DFS.)_
- What if cells wrap around the edges (toroidal grid)? _(Tests modular arithmetic for row/column indices.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_island_counter)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.