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
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#
- Rust
- Java 2
- Java 3
- C++ 2
- C++ 3
- Python 2
- Python 3
- Go 2
- Go 3
- TypeScript 2
- TypeScript 3
- Rust 2
- Rust 3
-
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 } } -
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 { 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}; 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; } }; -
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; } }; -
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 -
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]) 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 } -
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; 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; } -
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; } -
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 } } -
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 } }