Computer Science
Updated 23 days ago | GitHub

Counting Landmasses

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.

  • Input: grid = [[β€œ1”, β€œ1”, β€œ0”, β€œ0”, β€œ0”], [β€œ1”, β€œ1”, β€œ0”, β€œ0”, β€œ0”], [β€œ0”, β€œ0”, β€œ1”, β€œ0”, β€œ0”], [β€œ0”, β€œ0”, β€œ0”, β€œ1”, β€œ1”]]

    • Scan reaches (0, 0), a "1": DFS sinks the 2x2 block at rows 0-1, columns 0-1. island_count = 1.
    • Scan reaches (2, 2), a "1": DFS sinks just that cell (its horizontal/vertical neighbors are all water). island_count = 2.
    • Scan reaches (3, 3), a "1": DFS sinks (3, 3) and (3, 4). island_count = 3.
    • No "1" cells remain.
    • Output: 3

  • Input: grid = [[β€œ0”, β€œ0”], [β€œ0”, β€œ0”]]

    • The scan never finds a "1", so DFS is never called.
    • Output: 0

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.