# Find Number of Islands in 2D Map

Finding Number of Islands is a common problem in computer science, where the task is to determine the number of distinct islands in a 2-dimensional grid. In this problem, the grid is represented as a 2D matrix, where each cell can have a value of either `0` or `1`. Value of `1` represents land, and a `0` represents water. An island is defined as a group or cluster of connected land cells (represented by `1`s) in the 2D matrix. These land cells are considered connected if they are adjacent to each other horizontally or vertically, but not diagonally.

For example, consider the below graph/map:

``````1 1 0 0 0
1 1 0 0 0
0 0 0 0 0
0 0 0 1 1
``````

In this matrix, there are two islands:

• Island 1: The four `1`s in the top-left corner
• Island 2: The two `1`s in the bottom-right corner

Let’s consider another sample graph/map:

``````1 1 0 1 0
1 0 0 0 0
0 0 1 0 1
0 0 0 0 1
``````

This matrix contains four islands:

• Island 1: The three `1`s in the top-left corner
• Island 2: The single `1` near the top-right corner
• Island 3: The single `1` near the middle
• Island 4: The two `1`s near the bottom right corner

Let’s consider one other example graph/map:

``````1 1 0
0 0 1
0 0 1
``````

This matrix contains two islands:

• Island 1: The two `1`s in the top-left corner
• Island 2: The two `1`s in the bottom-right corner. Even though the two `1`s near the top right of the grid seem to be diagonally close, they can’t be considered and connected. Only horizontal or vertical connections are considered to be connected.

In order to solve this problem programmatically, we need to think of the 2D matrix as a graph, where each cell is a node, and the cells that are adjacent (up, down, left, right) are considered connected. There are two common approaches to solving this problem: Depth-First Search (DFS) and Breadth-First Search (BFS).

## Depth First Search Approach

Below the implementation of a depth-first search (DFS) algorithm to find the number of islands in a 2D grid:

``````
def dfs(grid, row, column):
"""
Perform depth-first search (DFS) to mark all connected land cells as visited.

Args:
grid: The 2D grid/map to be searched.
row: The current row index.
col: The current column index.
"""

# Check if the current cell is out of bounds or is already visited (0)
if row < 0 or row >= len(grid) or column < 0 or column >= len(grid[0]) or grid[row][column] == 0:
return

# Mark the current cell as visited (0)
grid[row][column] = 0

# Recursively call DFS on the neighboring cells
dfs(grid, row + 1, column)
dfs(grid, row - 1, column)
dfs(grid, row, column + 1)
dfs(grid, row, column - 1)

def count_islands(grid):
"""
Count the number of islands in a given grid.

Args:
grid: A 2D list representing the grid/map, where 1 is land and 0 is water.

Returns:
int: The total number of islands in the grid.
"""

# Check if the grid is empty
if not grid:
return 0

# Initialize the island count to 0
island_count = 0

# Iterate through each cell in the grid
for row in range(len(grid)):
for column in range(len(grid[0])):
# If the current cell is land (1)
if grid[row][column] == 1:
# Perform a depth-first search (DFS) and
# mark all connected land cells as visited (0)
dfs(grid, row, column)
# Increment the island count
island_count += 1

# Return the total number of islands
return island_count

# Example usage
grid = [
[1, 1, 0, 1, 0],
[1, 0, 0, 0, 0],
[0, 0, 1, 0, 1],
[0, 0, 0, 0, 1]
]

print(count_islands(grid))  # Output: 4
``````

In the above implementation, we modified the input grid and changed the value from `1` to `0` after we visited each land cell. If you do not wish to change the input, you can use a `visited` and add/check visited co-ordinates (row, column) to this set. BFS implementation given below contains hints on how you can do this.

## Breadth First Search Approach

Below the implementation of a Breadth-first search (BFS) algorithm to find the number of islands in a 2D grid:

``````
from collections import deque

def bfs(row, column, grid, visited):
"""
Perform breadth-first search (BFS) to mark all connected land cells as visited.

Args:
row: The current row index.
col: The current column index.
grid: The 2D grid/map to be searched.
visited: Set containing list of all visited coordinates
"""

# Create a queue to store the cells to be visited
queue = deque([(row, column)])

# Mark the current cell as visited

# Iterate until the queue is empty
while queue:
# Dequeue a cell from the queue
r, c = queue.popleft()

# Check the neighboring cells (up, down, left, right)
for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
next_r, next_c = r + dr, c + dc

# If the new cell is within the grid and is a land (1)
if 0 <= next_r < len(grid) and 0 <= next_c < len(grid[0]) and grid[next_r][next_c] == 1:
# If the new cell has not been visited, add it to the queue and mark it as visited
if (next_r, next_c) not in visited:
queue.append((next_r, next_c))

def count_islands(grid):
"""
Count the number of islands in a given grid.

Args:
grid: A 2D list representing the grid/map, where 1 is land and 0 is water.

Returns:
int: The total number of islands in the grid.
"""

# If the grid is empty, return 0
if not grid:
return 0

# Get the dimensions of the grid
rows, cols = len(grid), len(grid[0])

# Initialize the number of islands to 0
islands = 0

# Create a set to store the visited cells
visited = set()

# Iterate through the grid
for row in range(rows):
for column in range(cols):
# If the current cell is a land (1) and has not been visited
if grid[row][column] == 1 and (row, column) not in visited:
# Perform BFS on the current cell and increment the number of islands
bfs(row, column, grid, visited)
islands += 1

# Return the total number of islands
return islands

# Example usage
grid = [
[1, 1, 0, 1, 0],
[1, 0, 0, 0, 0],
[0, 0, 1, 0, 1],
[0, 0, 0, 0, 1]
]

print(count_islands(grid))  # Output: 4
``````

If you are allowed to change the grid, you can also set all visited island cells to `0` like we did in DFS approach.

## Time & Space Complexity

Both the DFS and BFS approaches have a time complexity of `O(m*n)`, where `m` and `n` are the dimensions of the 2D matrix, as we need to visit each cell at least once. The space complexity for the DFS approach is `O(m*n)` in the worst case (If we consider the extra space used to store visited information. If the grid can be modified, this can be ignored).