Welcome to Subscribe On Youtube

200. Number of Islands

Description

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'.

Solutions

DFS, BFS or Union find.

Flood fill, also called seed fill, is a flooding algorithm that determines and alters the area connected to a given node in a multi-dimensional array with some matching attribute. It is used in the “bucket” fill tool of paint programs to fill connected, similarly-colored areas with a different color.

Similar to UF in 305-Number-of-Islands-II/

• Java
• C++
• Python
• Go
• TypeScript
• C#
• RenderScript

• class Solution {
      private char[][] grid;
      private int m;
      private int n;
  
      public int numIslands(char[][] grid) {
          m = grid.length;
          n = grid[0].length;
          this.grid = grid;
          int ans = 0;
          for (int i = 0; i < m; ++i) {
              for (int j = 0; j < n; ++j) {
                  if (grid[i][j] == '1') {
                      dfs(i, j);
                      ++ans;
                  }
              }
          }
          return ans;
      }
  
      private void dfs(int i, int j) {
          grid[i][j] = '0';
          int[] dirs = {-1, 0, 1, 0, -1};
          for (int k = 0; k < 4; ++k) {
              int x = i + dirs[k];
              int y = j + dirs[k + 1];
              if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') {
                  dfs(x, y);
              }
          }
      }
  }
  
  //////
  
  class Solution {
      private char[][] grid;
      private int m;
      private int n;
  
      public int numIslands(char[][] grid) {
          m = grid.length;
          n = grid[0].length;
          this.grid = grid;
          int ans = 0;
          for (int i = 0; i < m; ++i) {
              for (int j = 0; j < n; ++j) {
                  if (grid[i][j] == '1') {
                      bfs(i, j);
                      ++ans;
                  }
              }
          }
          return ans;
      }
  
      private void bfs(int i, int j) {
          grid[i][j] = '0';
          Deque<int[]> q = new ArrayDeque<>();
          q.offer(new int[] {i, j});
          int[] dirs = {-1, 0, 1, 0, -1};
          while (!q.isEmpty()) {
              int[] p = q.poll();
              for (int k = 0; k < 4; ++k) {
                  int x = p[0] + dirs[k];
                  int y = p[1] + dirs[k + 1];
                  if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') {
                      q.offer(new int[] {x, y});
                      grid[x][y] = '0';
                  }
              }
          }
      }
  }
  
  

• class Solution {
  public:
      int numIslands(vector<vector<char>>& grid) {
          int m = grid.size();
          int n = grid[0].size();
          int ans = 0;
          int dirs[5] = {-1, 0, 1, 0, -1};
          function<void(int, int)> dfs = [&](int i, int j) {
              grid[i][j] = '0';
              for (int k = 0; k < 4; ++k) {
                  int x = i + dirs[k], y = j + dirs[k + 1];
                  if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() && grid[x][y] == '1') {
                      dfs(x, y);
                  }
              }
          };
          for (int i = 0; i < m; ++i) {
              for (int j = 0; j < n; ++j) {
                  if (grid[i][j] == '1') {
                      dfs(i, j);
                      ++ans;
                  }
              }
          }
          return ans;
      }
  };
  
  //////
  
  class Solution {
  public:
      int numIslands(vector<vector<char>>& grid) {
          int m = grid.size();
          int n = grid[0].size();
          int ans = 0;
          int dirs[5] = {-1, 0, 1, 0, -1};
          function<void(int, int)> bfs = [&](int i, int j) {
              grid[i][j] = '0';
              queue<pair<int, int>> q;
              q.push({i, j});
              vector<int> dirs = {-1, 0, 1, 0, -1};
              while (!q.empty()) {
                  auto [a, b] = q.front();
                  q.pop();
                  for (int k = 0; k < 4; ++k) {
                      int x = a + dirs[k];
                      int y = b + dirs[k + 1];
                      if (x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() && grid[x][y] == '1') {
                          q.push({x, y});
                          grid[x][y] = '0';
                      }
                  }
              }
          };
          for (int i = 0; i < m; ++i) {
              for (int j = 0; j < n; ++j) {
                  if (grid[i][j] == '1') {
                      bfs(i, j);
                      ++ans;
                  }
              }
          }
          return ans;
      }
  };
  
  

• # dfs
  class Solution:
      def numIslands(self, grid: List[List[str]]) -> int:
          def dfs(i, j):
              if not (0 <= i < m and 0 <= j < n and grid[i][j] == '1'):
                  return
              grid[i][j] = '0'
              for a, b in pairwise(dirs):
                  x, y = i + a, j + b
                  dfs(x, y)
  
          ans = 0
          dirs = (-1, 0, 1, 0, -1)
          m, n = len(grid), len(grid[0])
          for i in range(m):
              for j in range(n):
                  if grid[i][j] == '1':
                      dfs(i, j)
                      ans += 1
          return ans
  
  ###############
  
  # bfs
  from collections import deque
  
  class Solution:
      def numIslands(self, grid: List[List[str]]) -> int:
          if not grid:
              return 0
  
          m, n = len(grid), len(grid[0])
          directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
          islands = 0
  
          for i in range(m):
              for j in range(n):
                  if grid[i][j] == "1":
                      islands += 1
                      q = deque([(i, j)]) # no need to reset q, q already drained from previous bfs
                      while q:
                          x, y = q.popleft()
                          for dx, dy in directions:
                              nx, ny = x + dx, y + dy
                              if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == "1":
                                  q.append((nx, ny))
                                  grid[nx][ny] = "0"  # mark as visited
          return islands
  
  ###############
  
  # union find
  # similar to UF in https://leetcode.ca/2016-09-30-305-Number-of-Islands-II/
  class Solution:
      def numIslands(self, grid: List[List[str]]) -> int:
          def check(i, j):
              return 0 <= i < m and 0 <= j < n and grid[i][j] == "1"  # Check for "1" instead of 1
  
          def find(x):
              if p[x] != x:
                  p[x] = find(p[x])
              return p[x]
  
          m, n = len(grid), len(grid[0])
          p = list(range(m * n))
          cur = 0  # Initialize cur as 0 instead of n
          for i in range(m):
              for j in range(n):
                  if grid[i][j] == "1":
                      cur += 1  # Increment cur when encountering "1"
                      for x, y in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                          if check(i + x, j + y) and find(i * n + j) != find((i + x) * n + j + y):
                              p[find(i * n + j)] = find((i + x) * n + j + y)
                              cur -= 1
  
          return cur
  
  
  ############
  
  '''
  >>> a = set()
  >>>
  >>> a |= {(1, 1)}
  >>> a
  {(1, 1)}
  >>>
  >>> a |= {(2, 2)}
  >>> a
  {(1, 1), (2, 2)}
  >>>
  >>> a.add((3, 3))
  >>> a
  {(1, 1), (3, 3), (2, 2)}
  >>>
  >>> (1,1) in a
  True
  >>> (10,10) in a
  False
  '''
  class Solution(object):
    def numIslands(self, grid):
      """
      :type grid: List[List[str]]
      :rtype: int
      """
      visited = set()
      ans = 0
  
      def dfs(grid, i, j, visited):
        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == "0" or (i, j) in visited:
          return False
        visited |= {(i, j)}
        for di, dj in [(-1, 0), (1, 0), (0, 1), (0, -1)]:
          newi, newj = i + di, j + dj
          dfs(grid, newi, newj, visited)
        return True
  
      for i in range(0, len(grid)):
        for j in range(0, len(grid[0])):
          if dfs(grid, i, j, visited):
            ans += 1
      return ans
  
  

• func numIslands(grid [][]byte) int {
  	m, n := len(grid), len(grid[0])
  	var dfs func(i, j int)
  	dfs = func(i, j int) {
  		grid[i][j] = '0'
  		dirs := []int{-1, 0, 1, 0, -1}
  		for k := 0; k < 4; k++ {
  			x, y := i+dirs[k], j+dirs[k+1]
  			if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' {
  				dfs(x, y)
  			}
  		}
  	}
  	ans := 0
  	for i := 0; i < m; i++ {
  		for j := 0; j < n; j++ {
  			if grid[i][j] == '1' {
  				dfs(i, j)
  				ans++
  			}
  		}
  	}
  	return ans
  }
  

• function numIslands(grid: string[][]): number {
      const m = grid.length;
      const n = grid[0].length;
      let ans = 0;
      function dfs(i, j) {
          grid[i][j] = '0';
          const dirs = [-1, 0, 1, 0, -1];
          for (let k = 0; k < 4; ++k) {
              const x = i + dirs[k];
              const y = j + dirs[k + 1];
              if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') {
                  dfs(x, y);
              }
          }
      }
      for (let i = 0; i < m; ++i) {
          for (let j = 0; j < n; ++j) {
              if (grid[i][j] == '1') {
                  dfs(i, j);
                  ++ans;
              }
          }
      }
      return ans;
  }
  
  

• using System;
  using System.Collections.Generic;
  using System.Linq;
  
  public class Solution {
      public int NumIslands(char[][] grid)
      {
          var queue = new Queue<Tuple<int, int>>();
          var lenI = grid.Length;
          var lenJ = lenI == 0 ? 0 : grid[0].Length;
          var paths = new int[,] { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
          var result = 0;
          for (var i = 0; i < lenI; ++i)
          {
              for (var j = 0; j < lenJ; ++j)
              {
                  if (grid[i][j] == '1')
                  {
                      ++result;
                      grid[i][j] = '0';
                      queue.Enqueue(Tuple.Create(i, j));
                      while (queue.Any())
                      {
                          var position = queue.Dequeue();
                          for (var k = 0; k < 4; ++k)
                          {
                              var next = Tuple.Create(position.Item1 + paths[k, 0], position.Item2 + paths[k, 1]);
                              if (next.Item1 >= 0 && next.Item1 < lenI && next.Item2 >= 0 && next.Item2 < lenJ && grid[next.Item1][next.Item2] == '1')
                              {
                                  grid[next.Item1][next.Item2] = '0';
                                  queue.Enqueue(next);
                              }
                          }
                      }
                  }
              }
          }
          return result;
      }
  }
  

• const DIRS: [i32; 5] = [-1, 0, 1, 0, -1];
  
  impl Solution {
      pub fn num_islands(grid: Vec<Vec<char>>) -> i32 {
          fn dfs(grid: &mut Vec<Vec<char>>, i: usize, j: usize) {
              grid[i][j] = '0';
              for k in 0..4 {
                  let x = (i as i32) + DIRS[k];
                  let y = (j as i32) + DIRS[k + 1];
                  if
                      x >= 0 &&
                      (x as usize) < grid.len() &&
                      y >= 0 &&
                      (y as usize) < grid[0].len() &&
                      grid[x as usize][y as usize] == '1'
                  {
                      dfs(grid, x as usize, y as usize);
                  }
              }
          }
  
          let mut grid = grid;
          let mut ans = 0;
          for i in 0..grid.len() {
              for j in 0..grid[0].len() {
                  if grid[i][j] == '1' {
                      dfs(&mut grid, i, j);
                      ans += 1;
                  }
              }
          }
          ans
      }
  }
  
  

All Problems

All Solutions