MEDIUM
DATA STRUCTURES AND ALGORITHMS

# How to solve the Number of Islands Problem

ARRAYSSORTINGDEPTH FIRST SEARCH (DFS)BREADTH FIRST SEARCH (BFS)MATRICESUNION FIND
Written By Tom Wagner Kenny Polyak

## Introduction Number of Islands

The Number of Islands problem involves identifying contiguous land as represented on a two-dimensional grid. The grid is composed of 1s and 0s, where 1s represent land and 0s represent water, so solutions to this problem require a grasp of traversal algorithms such as depth-first search, breadth-first search, and union-find.

## Problem Number of Islands

Given a 2D matrix, where "1" represents land and "0" represents water, count how many islands are present. An island is a contiguous piece of land, where cells are connected by at least one of four cardinal directions (up, down, left, right), surrounded by water. We can assume the space beyond the borders is water.

### Example Inputs and Outputs

#### Example 1

Input: grid = [ ["0","0","1","1","0"], ["1","1","1","1","0"], ["0","1","0","0","0"], ["0","0","0","0","0"] ] Output: 1

Input: grid = [ ["1","0","1","1","1"], ["0","0","1","1","0"], ["0","1","0","0","0"], ["0","0","0","1","1"] ]

Output: 3

Constraints

• `1 <= grid.length <= 100`
• `1 <= grid.length[i] <= 100`

## Solution Number of Islands

Watch Someone Solve Number of Islands
Apple InterviewPython Interview
Advance this person to the next round?  Technical Skills:
4/4
Problem Solving Ability:
3/4
Communication Ability:
3/4

### Problem Approaches

This is a commonly given matrix problem, but it demands some creative problem solving. Although the solutions to this problem leverage some relatively common algorithms, how you communicate your thought process when choosing to apply them is a big part of what an interviewer will be assessing.

Like with all complex problems, let's start by first approaching the problem naively. To determine which cells are land, our algorithm will necessarily need to traverse the entire matrix in order to check the value of each element. Therefore, we can't do better than linear time, which in the case of a two-dimensional matrix, is `O(n * m)`.

While traversing the matrix, how do we track the number of clusters of "1"s and determine which land belongs to which islands? Remember that two adjacent “1”s are part of the same island, so if we were to traverse using two nested loops, starting from the top-left and ending at the bottom-right, we'll likely visit land later in the iteration that belongs to an island that was previously discovered. In this case, we would need a way to know what island a particular land cell belongs to. We would also need to know when an island is fully explored so we can add to our number of islands tally.

To avoid this, let's consider exhausting the exploration of each island once a piece of land is encountered, and once complete, we can simply add 1 to our running count of islands. We know for certain that an island is surrounded by water, so we would just need a way to explore all adjacent lands until there are none left.

What kind of traversal algorithm would be useful to discover all adjacent lands? A useful mental model here is that a matrix can be expressed using a graph data structure. While there are many ways to represent a graph computationally, a two-dimensional matrix lends itself well to a highly structured and connected graph: we can imagine that each element in a matrix is a graph node, connected via edges to its adjacent elements, moving left, up, right, down, and sometimes diagonally. You might see where this is going - we can use common graph traversal algorithms to our advantage: depth-first search (DFS) and breadth-first search (BFS).

Once a "1" is encountered, we can treat this as a "root" node and perform a traversal over each adjacent "1" until exhaustion. We'll also need to mark these elements as already-visited, since we know these land cells belong to an already accounted-for island. We can either track where we've been with a set of coordinates, or just transform visited lands into water so they are "ignored" as the iteration continues. Once an island exploration is complete, we increment our tally of numbers of islands, and simply continue the linear scan until another "1" is discovered.

#### Approach 1: Depth-First Search (DFS)

Depth-First Search (DFS) is an essential arrow in an engineer's problem-solving quiver. While there are many implementations, it is at its core a recognizable recursive algorithm (one that can also be expressed using a stack) that includes:

• a base case to stop the recursion -> if the cell we are trying to visit is out of bounds or a water cell.
• a way to know where to go next -> we want to check all adjacent cells (up, right, down, left).

For our island search, we'll perform a linear scan over the 2-dimensional grid with two nested for-loops, and if a cell is water we'll kick off our DFS, making sure to mark all waters as land so we never revisit. In the end, we are essentially just counting the number of times DFS is called from within the scope of the two for-loops.

``````class Solution:
def dfs(self, row: int, col: int, grid: List[List[str]]):
# base case
if self.is_inbounds(grid, row, col):
# transform land into water so we don't revisit this cell.
grid[row][col] = "0"

for new_row, new_col in [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]:
self.dfs(new_row, new_col, grid)

# validation: row and col are within the grid and the cell is a land.
def is_inbounds(self, grid: List[List[str]], row: int, col: int) -> bool:
return row >= 0 and row < len(grid) and col >= 0 and col < len(grid) and grid[row][col] == "1"

def numIslands(self, grid: List[List[str]]) -> int:
count = 0
num_rows = len(grid)
num_cols = len(grid)

for row in range(0, num_rows):
for col in range(0, num_cols):
if grid[row][col] == "1":
count += 1
self.dfs(row, col, grid)

return count
``````

#### Time/Space Complexity

• Time complexity: `O(n * m)`, where `n` is the number of rows and `m` is the number of columns.
• Space complexity: `O(m * n)`. In the worst case, where the entire grid is filled with lands, the call stack will grow to the number of cells in the grid.

#### Approach 2: Breadth-First Search (BFS)

Breadth-First Search (BFS) in this case accomplishes the same goal as DFS - exhausting all adjacent water cells - but through a different mechanism. Instead of always going to the furthest edges of the island when traversing, BFS explores all adjacent cells first, sort of like a single level, before moving on. This is accomplished using a queue, so that the order in which cells are visited remains level-by-level.

Like our DFS solution, we'll still need to mark visited lands by transforming them into water, and we'll ultimately tally the number of islands by counting how many times BFS is initiated from the linear nested for-loop scan.

``````class Solution:
# validation: row and col are within the grid and the cell is a land.
def is_inbounds(self, grid: List[List[str]], row: int, col: int) -> bool:
return row >= 0 and row < len(grid) and col >= 0 and col < len(grid) and grid[row][col] == "1"

def bfs(self, row: int, col: int, grid: List[List[str]]):
q = collections.deque()
q.append((row, col))
grid[row][col] = "0"

while q:
# visit the node
row, col = q.popleft()

for new_row, new_col in [(row + 1, col), (row, col + 1), (row - 1, col), (row, col - 1)]:
if self.is_inbounds(grid, new_row, new_col):
grid[new_row][new_col] = "0"
q.append((new_row, new_col))

def numIslands(self, grid: List[List[str]]) -> int:
count = 0
num_rows = len(grid)
num_cols = len(grid)

for row in range(0, num_rows):
for col in range(0, num_cols):
if grid[row][col] == "1":
count += 1
self.bfs(row, col, grid)

return count
``````

#### Time/Space Complexity

• Time complexity: `O(n * m)`, where `n` is the number of rows and `m` is the number of columns.
• Space complexity: `O(min(n, m)`. In the worst case, where the grid is entirely lands, the size of the queue will be bounded by either the row or column size before cells are processed.

## Practice Questions Similar to Number of Islands

MEDIUM
Data Structures and Algorithms
Build a Max Heap

Given an array of integers, transform the array in-place to a max heap.

Watch 1 interview
MEDIUM
Data Structures and Algorithms
Three Sum

Given an array of integers, return an array of triplets such that i != j != k and nums[i] + nums[j] + nums[k] = 0.

Watch 1 interview
EASY
Data Structures and Algorithms