Problem 26 - Number of Islands

Explore our archive for previous posts.

Question

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

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

Example 2:

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

Constraints:

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 300

• grid[i][j] is '0' or '1'.

Approach

The solution uses a depth-first search (DFS) approach to count the number of islands in the given grid. It iterates through each cell in the grid and, if it encounters land (cell with a value of '1'), it marks the land as visited and performs a DFS to explore the neighboring cells connected to the current land. By marking the visited land cells as '0' to prevent revisiting, it ensures that each island is counted only once.

The algorithm starts by checking for edge cases, such as an empty grid. Then, it iterates through each cell in the grid, and for each land cell encountered ('1'), it increments the island count and performs a DFS to visit all the connected land cells. The DFS explores the neighboring cells recursively in the top, bottom, left, and right directions, marking them as visited.

Solution

Solve it here

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0; // Empty grid, so no islands
        }

        int m = grid.length; // Number of rows
        int n = grid[0].length; // Number of columns
        int count = 0; // Count of islands

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    // Depth-First Search to visit connected land
                    dfs(grid, i, j); 
                }
            }
        }

        return count;
    }

    private void dfs(char[][] grid, int row, int col) {
        int m = grid.length;
        int n = grid[0].length;

        if (row < 0 || col < 0 || row >= m || col >= n || grid[row][col] != '1') {
            return; // Out of bounds or not a land cell
        }

        grid[row][col] = '0'; // Mark the current land cell as visited

        // Explore the neighboring cells recursively
        dfs(grid, row - 1, col); // Top
        dfs(grid, row + 1, col); // Bottom
        dfs(grid, row, col - 1); // Left
        dfs(grid, row, col + 1); // Right
    }
}

Time and space complexity

Time Complexity: The time complexity of the solution is O(m * n), where 'm' is the number of rows and 'n' is the number of columns in the grid. The algorithm visits each cell in the grid once, performing constant-time operations at each step.

Space Complexity: The space complexity is O(m * n) as the recursion depth can go up to the maximum number of cells in the grid. In the worst case, when the grid consists of all land cells ('1'), the DFS can explore all the cells, leading to a stack depth of m * n.

Explore more?

Missed a previous edition? Catch up on the insightful content you might have missed by visiting our archive here. Thank you for being a valued reader of our newsletter. We appreciate your continued support!