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 1s) 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:

In this matrix, there are two islands:

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

Let’s consider another sample graph/map:

This matrix contains four islands:

Island 1: The three 1s 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 1s 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 1s in the top-left corner
Island 2: The two 1s in the bottom-right corner. Even though the two 1s 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


#include <iostream>
#include <vector>

using namespace std;

// Function to perform depth-first search (DFS) to mark all connected land cells as visited
void dfs(vector<vector<int>>& grid, int row, int col) {
  // Check if the current cell is out of bounds or is already visited (0)
  if (row < 0 || row >= grid.size() || col < 0 || col >= grid[0].size() || grid[row][col] == 0) {
    return;
  }

  // Mark the current cell as visited (0)
  grid[row][col] = 0;

  // Recursively call DFS on the neighboring cells
  dfs(grid, row + 1, col);
  dfs(grid, row - 1, col);
  dfs(grid, row, col + 1);
  dfs(grid, row, col - 1);
}

// Function to count the number of islands in a given grid
int countIslands(vector<vector<int>>& grid) {
  // Check if the grid is empty
  if (grid.empty()) {
    return 0;
  }

  // Initialize the island count to 0
  int islandCount = 0;

  // Iterate through each cell in the grid
  for (int row = 0; row < grid.size(); row++) {
    for (int col = 0; col < grid[0].size(); col++) {
      // If the current cell is land (1)
      if (grid[row][col] == 1) {
        // Perform a depth-first search (DFS) and
        // mark all connected land cells as visited (0)
        dfs(grid, row, col);
        // Increment the island count
        islandCount++;
      }
    }
  }

  // Return the total number of islands
  return islandCount;
}

int main() {
  // Example usage
  vector<vector<int>> grid = {
    {1, 1, 0, 1, 0},
    {1, 0, 0, 0, 0},
    {0, 0, 1, 0, 1},
    {0, 0, 0, 0, 1}
  };

  cout << countIslands(grid) << endl;  // Output: 4
  return 0;
}


/**
 * Perform depth-first search (DFS) to mark all connected land cells as visited.
 * 
 * @param {number[][]} grid - The 2D grid/map to be searched.
 * @param {number} row - The current row index.
 * @param {number} col - The current column index.
 */
function dfs(grid, row, col) {
  // Check if the current cell is out of bounds or is already visited (0)
  if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] === 0) {
    return;
  }

  // Mark the current cell as visited (0)
  grid[row][col] = 0;

  // Recursively call DFS on the neighboring cells
  dfs(grid, row + 1, col);
  dfs(grid, row - 1, col);
  dfs(grid, row, col + 1);
  dfs(grid, row, col - 1);
}

/**
 * Count the number of islands in a given grid.
 * 
 * @param {number[][]} grid - A 2D list representing the grid/map, where 1 is land and 0 is water.
 * @returns {number} - The total number of islands in the grid.
 */
function countIslands(grid) {
  // Check if the grid is empty
  if (grid.length === 0) {
    return 0;
  }

  // Initialize the island count to 0
  let islandCount = 0;

  // Iterate through each cell in the grid
  for (let row = 0; row < grid.length; row++) {
    for (let col = 0; col < grid[0].length; col++) {
      // If the current cell is land (1)
      if (grid[row][col] === 1) {
        // Perform a depth-first search (DFS) and
        // mark all connected land cells as visited (0)
        dfs(grid, row, col);
        // Increment the island count
        islandCount++;
      }
    }
  }

  // Return the total number of islands
  return islandCount;
}

// Example usage
const grid = [
  [1, 1, 0, 1, 0],
  [1, 0, 0, 0, 0],
  [0, 0, 1, 0, 1],
  [0, 0, 0, 0, 1]
];

console.log(countIslands(grid)); // Output: 4


import java.util.*;

public class Main {
  
  // Perform depth-first search (DFS) to mark all connected land cells as visited
  public static void dfs(int[][] grid, int row, int col) {
    // Check if the current cell is out of bounds or is already visited (0)
    if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] == 0) {
      return;
    }

    // Mark the current cell as visited (0)
    grid[row][col] = 0;

    // Recursively call DFS on the neighboring cells
    dfs(grid, row + 1, col);
    dfs(grid, row - 1, col);
    dfs(grid, row, col + 1);
    dfs(grid, row, col - 1);
  }

  // Count the number of islands in a given grid
  public static int countIslands(int[][] grid) {
    // Check if the grid is empty
    if (grid == null || grid.length == 0) {
      return 0;
    }

    // Initialize the island count to 0
    int islandCount = 0;

    // Iterate through each cell in the grid
    for (int row = 0; row < grid.length; row++) {
      for (int col = 0; col < grid[0].length; col++) {
        // If the current cell is land (1)
        if (grid[row][col] == 1) {
          // Perform a depth-first search (DFS) and
          // mark all connected land cells as visited (0)
          dfs(grid, row, col);
          // Increment the island count
          islandCount++;
        }
      }
    }

    // Return the total number of islands
    return islandCount;
  }

  public static void main(String[] args) {
    int[][] grid = {
      {1, 1, 0, 1, 0},
      {1, 0, 0, 0, 0},
      {0, 0, 1, 0, 1},
      {0, 0, 0, 0, 1}
    };

    System.out.println(countIslands(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
  visited.add((row, column))
  
  # 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))
          visited.add((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


#include <iostream>
#include <queue>
#include <unordered_set>
using namespace std;

// Perform breadth-first search (BFS) to mark all connected land cells as visited
void bfs(int row, int column, vector<vector<int>>& grid, unordered_set<string>& visited) {
  // Create a queue to store the cells to be visited
  queue<pair<int, int>> q;
  q.push({row, column});

  // Mark the current cell as visited
  visited.insert(to_string(row) + "," + to_string(column));

  // Iterate until the queue is empty
  while (!q.empty()) {
    // Dequeue a cell from the queue
    int r = q.front().first;
    int c = q.front().second;
    q.pop();

    // Check the neighboring cells (up, down, left, right)
    for (auto [dr, dc] : vector<pair<int, int>>{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}) {
      int next_r = r + dr;
      int next_c = c + dc;

      // If the new cell is within the grid and is a land (1)
      if (0 <= next_r && next_r < grid.size() && 0 <= next_c && next_c < grid[0].size() && 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 (visited.find(to_string(next_r) + "," + to_string(next_c)) == visited.end()) {
          q.push({next_r, next_c});
          visited.insert(to_string(next_r) + "," + to_string(next_c));
        }
      }
    }
  }
}

// Function to count the number of islands in the grid
int count_islands(vector<vector<int>>& grid) {
  // If the grid is empty, return 0
  if (grid.empty()) {
    return 0;
  }

  // Get the dimensions of the grid
  int rows = grid.size();
  int cols = grid[0].size();

  // Initialize the number of islands to 0
  int islands = 0;

  // Create a set to store the visited cells
  unordered_set<string> visited;

  // Iterate through the grid
  for (int row = 0; row < rows; row++) {
    for (int column = 0; column < cols; column++) {
      // If the current cell is a land (1) and has not been visited
      if (grid[row][column] == 1 && visited.find(to_string(row) + "," + to_string(column)) == visited.end()) {
        // Perform BFS on the current cell and increment the number of islands
        bfs(row, column, grid, visited);
        islands++;
      }
    }
  }

  // Return the total number of islands
  return islands;
}

int main() {
  vector<vector<int>> grid = {
    {1, 1, 0, 1, 0},
    {1, 0, 0, 0, 0},
    {0, 0, 1, 0, 1},
    {0, 0, 0, 0, 1}
  };

  cout << count_islands(grid) << endl;  // Output: 4
  return 0;
}


/**
 * Perform breadth-first search (BFS) to mark all connected land cells as visited.
 * 
 * @param {number} row - The current row index.
 * @param {number} column - The current column index.
 * @param {number[][]} grid - The 2D grid/map to be searched.
 * @param {Set<string>} visited - Set containing list of all visited coordinates.
 */
function bfs(row, column, grid, visited) {
  // Create a queue to store the cells to be visited
  const queue = [[row, column]];

  // Mark the current cell as visited
  visited.add(`${row},${column}`);

  // Iterate until the queue is empty
  while (queue.length > 0) {
    // Dequeue a cell from the queue
    const [r, c] = queue.shift();

    // Check the neighboring cells (up, down, left, right)
    for (const [dr, dc] of [[0, 1], [0, -1], [1, 0], [-1, 0]]) {
      const nextR = r + dr;
      const nextC = c + dc;

      // If the new cell is within the grid and is a land (1)
      if (
        nextR >= 0 &&
        nextR < grid.length &&
        nextC >= 0 &&
        nextC < grid[0].length &&
        grid[nextR][nextC] === 1
      ) {
        // If the new cell has not been visited, add it to the queue and mark it as visited
        const key = `${nextR},${nextC}`;
        if (!visited.has(key)) {
          queue.push([nextR, nextC]);
          visited.add(key);
        }
      }
    }
  }
}

/**
 * Count the number of islands in a given grid.
 * 
 * @param {number[][]} grid - A 2D list representing the grid/map, where 1 is land and 0 is water.
 * @returns {number} - The total number of islands in the grid.
 */
function countIslands(grid) {
  // If the grid is empty, return 0
  if (grid.length === 0) {
    return 0;
  }

  // Get the dimensions of the grid
  const rows = grid.length;
  const cols = grid[0].length;

  // Initialize the number of islands to 0
  let islands = 0;

  // Create a set to store the visited cells
  const visited = new Set();

  // Iterate through the grid
  for (let row = 0; row < rows; row++) {
    for (let column = 0; column < cols; column++) {
      // If the current cell is a land (1) and has not been visited
      if (grid[row][column] === 1 && !visited.has(`${row},${column}`)) {
        // Perform BFS on the current cell and increment the number of islands
        bfs(row, column, grid, visited);
        islands++;
      }
    }
  }

  // Return the total number of islands
  return islands;
}

// Example usage
const grid = [
  [1, 1, 0, 1, 0],
  [1, 0, 0, 0, 0],
  [0, 0, 1, 0, 1],
  [0, 0, 0, 0, 1]
];

console.log(countIslands(grid)); // Output: 4


import java.util.LinkedList;
import java.util.Queue;
import java.util.HashSet;

public class Main {
  
  // Perform breadth-first search (BFS) to mark all connected land cells as visited
  public static void bfs(int row, int column, int[][] grid, HashSet<String> visited) {
    // Create a queue to store the cells to be visited
    Queue<int[]> queue = new LinkedList<>();
    queue.offer(new int[]{row, column});
    
    // Mark the current cell as visited
    visited.add(row + "," + column);
    
    // Iterate until the queue is empty
    while (!queue.isEmpty()) {
      // Dequeue a cell from the queue
      int[] curr = queue.poll();
      int r = curr[0], c = curr[1];
      
      // Check the neighboring cells (up, down, left, right)
      for (int[] dir : new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}) {
        int nextR = r + dir[0], nextC = c + dir[1];
        
        // If the new cell is within the grid and is a land (1)
        if (nextR >= 0 && nextR < grid.length && nextC >= 0 && nextC < grid[0].length && grid[nextR][nextC] == 1) {
          // If the new cell has not been visited, add it to the queue and mark it as visited
          if (!visited.contains(nextR + "," + nextC)) {
            queue.offer(new int[]{nextR, nextC});
            visited.add(nextR + "," + nextC);
          }
        }
      }
    }
  }
  
  // Count the number of islands in the grid
  public static int countIslands(int[][] grid) {
    // If the grid is empty, return 0
    if (grid == null || grid.length == 0) {
      return 0;
    }
    
    // Get the dimensions of the grid
    int rows = grid.length, cols = grid[0].length;
    
    // Initialize the number of islands to 0
    int islands = 0;
    
    // Create a set to store the visited cells
    HashSet<String> visited = new HashSet<>();
    
    // Iterate through the grid
    for (int row = 0; row < rows; row++) {
      for (int column = 0; column < cols; column++) {
        // If the current cell is a land (1) and has not been visited
        if (grid[row][column] == 1 && !visited.contains(row + "," + column)) {
          // Perform BFS on the current cell and increment the number of islands
          bfs(row, column, grid, visited);
          islands++;
        }
      }
    }
    
    // Return the total number of islands
    return islands;
  }
  
  public static void main(String[] args) {
    int[][] grid = {
      {1, 1, 0, 1, 0},
      {1, 0, 0, 0, 0},
      {0, 0, 1, 0, 1},
      {0, 0, 0, 0, 1}
    };
    
    System.out.println(countIslands(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).