Number of Islands — Coding Interview Question

In this post, we will walk through a solution for Leetcode problem “Number of Islands” in Java

Problem Statement

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.

Solution

Let’s follow systematic approach in solving this popular interview question.

First step in solving any problem is making sure we understand the problem correctly. Best way to understand the problem statement is to take an example, understand the input format and expected output for the given input.

In this case, we are given a 2D array which contains ‘0’s and ‘1’s. Hence, let’s take following 2D array as an example:

Example input 2D array

There are 3 islands as marked in red color for given 2D grid

Why Depth First Search ?

We can solve this problem using Depth First Search (DFS) algorithm. DFS suitable for this problem because:

1. We know that DFS can be used to traverse the grid/matrix (2D array).
2. Islands in the grid can be seen as connected components, where each component represents a group of adjacent land cells. DFS is an effective algorithm for exploring and identifying connected components in a graph or grid structure.
3. DFS explores a path as deeply as possible before backtracking. In the context of the problem, DFS allows us to traverse the land cells in a depth-first manner, moving from one land cell to its neighboring land cells until we exhaust all connected land cells of an island. This exploration strategy aligns well with the concept of islands in the problem.
4. When a DFS path reaches a dead end (no more neighboring land cells to explore), it backtracks to a previous cell to continue the exploration. In the problem, when DFS finishes exploring all the connected land cells of an island, it backtracks to the next unvisited land cell, continuing the process until all land cells are visited.

By leveraging DFS, we can systematically explore and mark all the connected land cells, counting each exploration as a separate island. DFS helps us traverse the grid and identify the distinct islands present within it.

Implementation

Following section provides a Java solution using Depth First Search for Number of Islands problem.

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int count = 0;
        int rows = grid.length;
        int columns = grid[0].length;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (grid[i][j] == '1') {
                    count++;  
                    dfs(grid, i, j); // Start exploring this Island using DFS
                }
            }
        }

        return count;
    }

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

        // check out of bounds, base case to stop exploring further
        if (row < 0 || row >= rows || col < 0 || col >= columns || grid[row][col] == '0') {
            return;
        }

        grid[row][col] = '0'; // Mark the current cell as visited, presuming we can change the input passed

        // For each neighbor, call DFS to explore further
        dfs(grid, row - 1, col); // Up
        dfs(grid, row + 1, col); // Down
        dfs(grid, row, col - 1); // Left
        dfs(grid, row, col + 1); // Right
    }

The DFS algorithm works as follows:

• For each land cell encountered, it explores its neighboring land cells using the dfs function, marking them as visited and continuing the exploration recursively.
• By doing so, it traverses the connected land cells of each island, effectively counting the number of islands in the grid.