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.lengthn == grid[i].length1 <= m, n <= 300grid[i][j]is'0'or'1'.
Solutions
Solution 1
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/
Solution 2: BFS
We can also use breadth-first search (BFS) to traverse each island. We iterate through each cell $(i, j)$ in the grid. If the cell’s value is ‘1’, it means we have found a new island. We can start a BFS from this cell, marking all connected land cells as ‘0’ to avoid duplicate counting. Each time we find a new island, we increment the island count by 1.
The specific BFS process is as follows:
- Enqueue the starting cell $(i, j)$ and mark its value as ‘0’.
- While the queue is not empty, perform the following operations:
- Dequeue a cell $p$.
- Iterate through the four adjacent cells $(x, y)$ of $p$. If $(x, y)$ is within the grid bounds and its value is ‘1’, enqueue it and mark its value as ‘0’.
The time complexity is $O(m \times n)$, and the space complexity is $O(m \times n)$. Where $m$ and $n$ are the number of rows and columns in the grid, respectively.
Solution 3: Union-Find
We can use the Union-Find data structure to solve this problem. We traverse each cell $(i, j)$ in the grid, and if the cell’s value is ‘1’, we merge it with adjacent land cells. Finally, we count the number of distinct root nodes in the Union-Find structure, which represents the number of islands.
The time complexity is $O(m \times n \times \log (m \times n))$, and the space complexity is $O(m \times n)$. Where $m$ and $n$ are the number of rows and columns in the grid, respectively.
-
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'; } } } } } // Solution 2 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'; } } } } } // Solution 3 class Solution { private int[] p; public int numIslands(char[][] grid) { int m = grid.length; int n = grid[0].length; p = new int[m * n]; for (int i = 0; i < p.length; ++i) { p[i] = i; } int[] dirs = {1, 0, 1}; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] == '1') { for (int k = 0; k < 2; ++k) { int x = i + dirs[k]; int y = j + dirs[k + 1]; if (x < m && y < n && grid[x][y] == '1') { p[find(x * n + y)] = find(i * n + j); } } } } } int ans = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] == '1' && i * n + j == find(i * n + j)) { ++ans; } } } return ans; } private int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; } } -
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; } }; // Solution 2 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}; auto bfs = [&](int i, int j) -> void { grid[i][j] = '0'; queue<pair<int, int>> q; q.push({i, j}); 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; } }; // Solution 3 class Solution { public: int numIslands(vector<vector<char>>& grid) { int m = grid.size(); int n = grid[0].size(); vector<int> p(m * n); iota(p.begin(), p.end(), 0); function<int(int)> find = [&](int x) -> int { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; }; int dirs[3] = {1, 0, 1}; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] == '1') { for (int k = 0; k < 2; ++k) { int x = i + dirs[k]; int y = j + dirs[k + 1]; if (x < m && y < n && grid[x][y] == '1') { p[find(x * n + y)] = find(i * n + j); } } } } } int ans = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { ans += grid[i][j] == '1' && i * n + j == find(i * n + j); } } 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 # Solution 2 class Solution: def numIslands(self, grid: List[List[str]]) -> int: def bfs(i, j): grid[i][j] = '0' q = deque([(i, j)]) while q: i, j = q.popleft() for a, b in pairwise(dirs): x, y = i + a, j + b if 0 <= x < m and 0 <= y < n and grid[x][y] == '1': q.append((x, y)) grid[x][y] = 0 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': bfs(i, j) ans += 1 return ans # Solution 3 class Solution: def numIslands(self, grid: List[List[str]]) -> int: def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] dirs = (0, 1, 0) m, n = len(grid), len(grid[0]) p = list(range(m * n)) for i in range(m): for j in range(n): if grid[i][j] == '1': for a, b in pairwise(dirs): x, y = i + a, j + b if x < m and y < n and grid[x][y] == '1': p[find(i * n + j)] = find(x * n + y) return sum( grid[i][j] == '1' and i * n + j == find(i * n + j) for i in range(m) for j in range(n) ) -
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 } // Solution 2 func numIslands(grid [][]byte) int { m, n := len(grid), len(grid[0]) bfs := func(i, j int) { grid[i][j] = '0' q := [][]int{[]int{i, j}} dirs := []int{-1, 0, 1, 0, -1} for len(q) > 0 { p := q[0] q = q[1:] for k := 0; k < 4; k++ { x, y := p[0]+dirs[k], p[1]+dirs[k+1] if x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' { q = append(q, []int{x, y}) grid[x][y] = '0' } } } } ans := 0 for i := 0; i < m; i++ { for j := 0; j < n; j++ { if grid[i][j] == '1' { bfs(i, j) ans++ } } } return ans } // Solution 3 func numIslands(grid [][]byte) int { m, n := len(grid), len(grid[0]) p := make([]int, m*n) for i := range p { p[i] = i } var find func(x int) int find = func(x int) int { if p[x] != x { p[x] = find(p[x]) } return p[x] } dirs := []int{1, 0, 1} for i := 0; i < m; i++ { for j := 0; j < n; j++ { if grid[i][j] == '1' { for k := 0; k < 2; k++ { x, y := i+dirs[k], j+dirs[k+1] if x < m && y < n && grid[x][y] == '1' { p[find(x*n+y)] = find(i*n + j) } } } } } ans := 0 for i := 0; i < m; i++ { for j := 0; j < n; j++ { if grid[i][j] == '1' && i*n+j == find(i*n+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; } // Solution 2 function numIslands(grid: string[][]): number { const m = grid.length; const n = grid[0].length; let ans = 0; const bfs = (i: number, j: number) => { grid[i][j] = '0'; const q = [[i, j]]; const dirs = [-1, 0, 1, 0, -1]; for (const [i, j] of q) { for (let k = 0; k < 4; ++k) { const x = i + dirs[k]; const y = j + dirs[k + 1]; if (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(i, j); ++ans; } } } return ans; } // Solution 3 function numIslands(grid: string[][]): number { const m = grid.length; const n = grid[0].length; const p: number[] = Array.from({ length: m * n }, (_, i) => i); function find(x: number): number { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; } const dirs = [1, 0, 1]; for (let i = 0; i < m; ++i) { for (let j = 0; j < n; ++j) { if (grid[i][j] == '1') { for (let k = 0; k < 2; ++k) { const x = i + dirs[k]; const y = j + dirs[k + 1]; if (grid[x]?.[y] == '1') { p[find(i * n + j)] = find(x * n + y); } } } } } let ans = 0; for (let i = 0; i < m; ++i) { for (let j = 0; j < n; ++j) { if (grid[i][j] == '1' && i * n + j == find(i * n + 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 } } // Solution 2 use std::collections::VecDeque; const DIRS: [i32; 5] = [-1, 0, 1, 0, -1]; impl Solution { pub fn num_islands(grid: Vec<Vec<char>>) -> i32 { fn bfs(grid: &mut Vec<Vec<char>>, i: usize, j: usize) { grid[i][j] = '0'; let mut queue = VecDeque::from([(i, j)]); while !queue.is_empty() { let (i, j) = queue.pop_front().unwrap(); 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' { grid[x as usize][y as usize] = '0'; queue.push_back((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' { bfs(&mut grid, i, j); ans += 1; } } } ans } } // Solution 3 const DIRS: [usize; 3] = [1, 0, 1]; impl Solution { pub fn num_islands(grid: Vec<Vec<char>>) -> i32 { let m = grid.len(); let n = grid[0].len(); let mut p: Vec<i32> = (0..(m * n) as i32).collect(); fn find(p: &mut Vec<i32>, x: usize) -> i32 { if p[x] != (x as i32) { p[x] = find(p, p[x] as usize); } p[x] } for i in 0..m { for j in 0..n { if grid[i][j] == '1' { for k in 0..2 { let x = i + DIRS[k]; let y = j + DIRS[k + 1]; if x < m && y < n && grid[x][y] == '1' { let f1 = find(&mut p, x * n + y); let f2 = find(&mut p, i * n + j); p[f1 as usize] = f2; } } } } } let mut ans = 0; for i in 0..m { for j in 0..n { if grid[i][j] == '1' && p[i * n + j] == ((i * n + j) as i32) { ans += 1; } } } ans } }