Skip to content

Counting Landmasses

Jump to bottom
Andrew Burke edited this page Aug 19, 2026 · 1 revision

TIP103 Unit 11 Session 1 (Click for link to problem statements)

Counting Landmasses

A satellite scan returns a grid of "1" (land) and "0" (water). An island is a group of land cells connected horizontally or vertically.

Given the grid, return the number of distinct islands.

def num_islands(grid):
    pass

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20-30 mins
  • 🛠️ Topics: Graphs, Depth-First Search (DFS), Connected Components, Matrix Traversal

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?

  • Q: What counts as a single island?

    • A: A maximal group of "1" (land) cells where each cell touches at least one other cell in the group horizontally or vertically.

  • Q: Do diagonal land cells belong to the same island?

    • A: No. Only horizontal and vertical neighbors are connected; two land cells touching only at a corner are separate islands.

  • Q: Are the grid values strings or integers?

    • A: They are the strings "1" and "0", so comparisons should be against "1", not the integer 1.
HAPPY CASE
Input: grid = [
    ["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 landmasses: the 2x2 block in the top-left corner, the lone cell at row 2 column 2, and the pair of cells at the bottom-right. The lone cell touches the bottom-right pair only diagonally, so they are separate islands.

EDGE CASE
Input: grid = [
    ["0", "0"],
    ["0", "0"],
]
Output: 0
Explanation: The scan found no land at all, so there are no islands.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Grid/Matrix Graph Traversal Problems, we can consider the following approaches:

  • DFS (Depth-First Search): Treat each cell as a node connected to its 4 neighbors, and "flood fill" an entire island from any of its cells.
  • BFS (Breadth-First Search): An iterative queue-based flood fill works just as well.
  • Union-Find (Disjoint Set): Union adjacent land cells and count the resulting components.

Counting connected components is the core pattern: every time we discover an unvisited land cell, we have found a new island.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Scan every cell of the grid. When we find a "1", we have discovered a new island: increment the count, then run a DFS flood fill from that cell that "sinks" every reachable land cell to "0" so no cell is ever counted twice.

1) If the grid is empty, return 0.
2) Define a DFS helper function on (row, col):
   a) If (row, col) is out of bounds or the cell is not "1", return.
   b) Set grid[row][col] = "0" to mark it visited (sink it).
   c) Recurse on the four neighbors: down, up, right, left.
3) Iterate over every cell in the grid:
   a) If the cell is "1", call DFS on it and increment the island count.
4) Return the island count.

⚠️ Common Mistakes

  • Comparing cells against the integer 1 instead of the string "1".
  • Forgetting to mark visited cells, causing the DFS to revisit cells and recurse forever.
  • Including diagonal neighbors in the traversal, which merges islands that should be separate.
  • Missing the bounds check before indexing into the grid, causing an index error.

4: I-mplement

Implement the code to solve the algorithm.

def num_islands(grid):
    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])

    def dfs(row, col):
        # Stop if out of bounds or the cell is water (or already visited)
        if row < 0 or row >= rows or col < 0 or col >= cols or grid[row][col] != "1":
            return
        # Sink the cell so it is not counted again
        grid[row][col] = "0"
        # Explore the four horizontal/vertical neighbors
        dfs(row + 1, col)
        dfs(row - 1, col)
        dfs(row, col + 1)
        dfs(row, col - 1)

    island_count = 0
    for row in range(rows):
        for col in range(cols):
            if grid[row][col] == "1":
                dfs(row, col)
                island_count += 1

    return island_count

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume M is the number of rows and N is the number of columns in the grid.

  • Time Complexity: O(M * N) because every cell is visited a constant number of times — once by the scan, and at most once by a DFS flood fill.
  • Space Complexity: O(M * N) in the worst case for the recursion stack, when the entire grid is one snake-shaped island. Note that this solution mutates the input grid to mark visited cells; if the input must be preserved, keep a separate visited set instead, which also uses O(M * N) space.

Clone this wiki locally