Table of contents

Find the Number of Islands

Given a 2D grid representing a map of 1s (land) and 0s (water), write a program to count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume that all four edges of the grid are surrounded by water.

Input/Output Examples

plaintext
Example 1:
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 islands in the grid. They are formed by connecting adjacent 1s.

Example 2:
Input: grid = 
[ [1, 0, 1, 1],
  [1, 0, 0, 0],
  [1, 1, 0, 1]
]

Output: 3
Explanation: There are three islands in the grid.

Approach to Find the Number of Islands 

  1. Grid Representation:
    • The grid is a 2D array where 1 represents land and 0 represents water. The task is to count how many distinct islands (connected components of 1s) exist in the grid.
  2. DFS/BFS Approach:
    • We can use Depth First Search (DFS) or Breadth First Search (BFS) to explore each island.
    • For every unvisited land cell (1), we initiate a DFS or BFS and mark all the cells that form part of the same island as visited.
    • Every time a new DFS/BFS starts, it corresponds to a new island.
  3. Marking Visited Cells:
    • We can mark cells as visited by changing their value in the grid from 1 to 0, or using a separate visited array.
  4. Edge Cases:
    • If the grid is empty, return 0.
    • If there are no 1s in the grid, return 0.

C++ Program to Find the Number of Islands 

cpp
#include <iostream>
#include <vector>
using namespace std;

// Directions array for exploring adjacent cells (up, down, left, right)
int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

// DFS function to explore the island
void dfs(vector<vector<int>>& grid, int i, int j, int rows, int cols) {
    // Base condition: if out of bounds or water, return
    if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] == 0) {
        return;
    }

    // Mark the current cell as visited by setting it to 0
    grid[i][j] = 0;

    // Explore all four possible directions (up, down, left, right)
    for (int d = 0; d < 4; d++) {
        int newRow = i + directions[d][0];
        int newCol = j + directions[d][1];
        dfs(grid, newRow, newCol, rows, cols);
    }
}

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

    int rows = grid.size();
    int cols = grid[0].size();
    int islandCount = 0;

    // Traverse each cell in the grid
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == 1) {  // Found a new island
                islandCount++;
                dfs(grid, i, j, rows, cols);  // Perform DFS to mark all connected land as visited
            }
        }
    }

    return islandCount;
}

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

    cout << "Number of islands: " << numIslands(grid) << endl;
    return 0;
}

Java Program to Find the Number of Islands 

java
public class NumberOfIslands {

    // Directions array for exploring adjacent cells (up, down, left, right)
    private static final int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    // DFS function to explore the island
    public static void dfs(int[][] grid, int i, int j) {
        int rows = grid.length;
        int cols = grid[0].length;

        // Base condition: if out of bounds or water, return
        if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] == 0) {
            return;
        }

        // Mark the current cell as visited by setting it to 0
        grid[i][j] = 0;

        // Explore all four possible directions (up, down, left, right)
        for (int[] direction : directions) {
            int newRow = i + direction[0];
            int newCol = j + direction[1];
            dfs(grid, newRow, newCol);
        }
    }

    // Function to count the number of islands in the grid
    public static int numIslands(int[][] grid) {
        if (grid.length == 0) return 0;

        int rows = grid.length;
        int cols = grid[0].length;
        int islandCount = 0;

        // Traverse each cell in the grid
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 1) {  // Found a new island
                    islandCount++;
                    dfs(grid, i, j);  // Perform DFS to mark all connected land as visited
                }
            }
        }

        return islandCount;
    }

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

        System.out.println("Number of islands: " + numIslands(grid));
    }
}

Python Program to Find the Number of Islands

python
# Directions array for exploring adjacent cells (up, down, left, right)
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

# DFS function to explore the island
def dfs(grid, i, j):
    rows, cols = len(grid), len(grid[0])

    # Base condition: if out of bounds or water, return
    if i < 0 or i >= rows or j < 0 or j >= cols or grid[i][j] == 0:
        return

    # Mark the current cell as visited by setting it to 0
    grid[i][j] = 0

    # Explore all four possible directions (up, down, left, right)
    for direction in directions:
        newRow, newCol = i + direction[0], j + direction[1]
        dfs(grid, newRow, newCol)

# Function to count the number of islands in the grid
def num_islands(grid):
    if not grid:
        return 0

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

    # Traverse each cell in the grid
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == 1:  # Found a new island
                island_count += 1
                dfs(grid, i, j)  # Perform DFS to mark all connected land as visited

    return island_count

# Example usage
if __name__ == "__main__":
    grid = [
        [1, 1, 0, 0, 0],
        [1, 1, 0, 0, 0],
        [0, 0, 1, 0, 0],
        [0, 0, 0, 1, 1]
    ]
    print("Number of islands:", num_islands(grid))
  • Time Complexity: O(rows * cols) where rows is the number of rows in the grid and cols is the number of columns. Each cell is processed once during the DFS.
  • Space Complexity: O(rows * cols) for the recursive call stack or the visited grid.

DSA

Related Articles