Number of Islands

---

Number of Islands: 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'.

---

Try this Problem on your own or check similar problems:

1. Surrounded Regions
2. Max Area of Island
3. Count Sub Islands

Solution:

Java

class Solution {
  public int numIslands(char[][] grid) {
      int numberofIslands = 0;
      for(int i = 0; i < grid.length; ++i){
          for(int j = 0; j < grid[0].length; ++j){
              if(grid[i][j] == '1'){
                  bfs(grid, new int[] {i, j});
                  ++numberofIslands;
              }
          }
      }
      return numberofIslands;
  }

  private void bfs(char[][] grid, int[] start){
      int[][] directions  = new int[][] { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1}};
      int m = grid.length, n = grid[0].length;
      Queue<int[]> q = new LinkedList<>();
      q.add(start);
      while(!q.isEmpty()){
          int[] current = q.poll();
          for(int[] d : directions){
              int x = current[0] + d[0];
              int y = current[1] + d[1];
              if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1'){
                  q.add(new int[] {x, y});
                  grid[x][y] = '0';
              }
          }
      }
  }
}

JavaScript

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
  let numberOfIslands = 0;
  const m = grid.length;
  const n = grid[0].length;

  const bfs = (grid, start) => {
    const directions = [
      [1, 0],
      [0, 1],
      [-1, 0],
      [0, -1],
    ];
    const q = [start];

    while (q.length > 0) {
      const current = q.shift();

      for (const d of directions) {
        const x = current[0] + d[0];
        const y = current[1] + d[1];

        if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] === "1") {
          q.push([x, y]);
          grid[x][y] = "0";
        }
      }
    }
  };

  for (let i = 0; i < m; ++i) {
    for (let j = 0; j < n; ++j) {
      if (grid[i][j] === "1") {
        bfs(grid, [i, j]);
        ++numberOfIslands;
      }
    }
  }

  return numberOfIslands;
};

Python

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def bfs(grid, start):
            directions = [[1, 0], [0, 1], [-1, 0], [0, -1]]
            m, n = len(grid), len(grid[0])
            q = deque([start])

            while q:
                current = q.popleft()

                for d in directions:
                    x = current[0] + d[0]
                    y = current[1] + d[1]

                    if 0 <= x < m and 0 <= y < n and grid[x][y] == '1':
                        q.append([x, y])
                        grid[x][y] = '0'

        numberOfIslands = 0
        m, n = len(grid), len(grid[0])

        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    bfs(grid, [i, j])
                    numberOfIslands += 1

        return numberOfIslands

C++

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int numberOfIslands = 0;
        int m = grid.size();
        int n = grid[0].size();


        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '1') {
                    bfs(grid, {i, j});
                    ++numberOfIslands;
                }
            }
        }

        return numberOfIslands;
    }

private:
    vector<vector<int>> directions = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    void bfs(vector<vector<char>>& grid, vector<int> start) {
        int m = grid.size();
        int n = grid[0].size();
        queue<vector<int>> q;
        q.push(start);

        while (!q.empty()) {
            vector<int> current = q.front();
            q.pop();

            for (const auto& d : directions) {
                int x = current[0] + d[0];
                int y = current[1] + d[1];

                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') {
                    q.push({x, y});
                    grid[x][y] = '0';
                }
            }
        }
    }
};

---

Time/Space Complexity:

• Time Complexity: O(m*n)
• Space Complexity: O(m*n)

---

Explanation:

We have almost the same BFS approach we had in the Pacific Atlantic Water Flow this time choosing neighbors only if the adjacent cell has the value of 1. Since we're only interested in the number of islands nothing is stopping us from marking the cell with value 1 with 0 after we have visited it. The two loops in the main function go over all the cells and we only choose to do BFS with cell that has value 1 as the starting cell/island. We keep track of the number of islands using the numberofIslands which we finally return from the function as our solution.