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
We can use depth-first search (DFS) 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 DFS 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 time complexity is O(m × n), and the space complexity is O(m × n). Where m and n are the number of rows and columns in the grid, respectively.
PythonJavaC++GoTypeScriptRustC#
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
def dfs(i, j):
grid[i][j] = '0'
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':
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(code-box)
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);
}
}
}
}(code-box)
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 dfs = [&](this auto&& dfs, int i, int j) -> void {
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;
}
};(code-box)
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
}(code-box)
function numIslands(grid: string[][]): number {
const m = grid.length;
const n = grid[0].length;
let ans = 0;
const dirs = [-1, 0, 1, 0, -1];
const dfs = (i: number, j: number) => {
grid[i][j] = '0';
for (let k = 0; k < 4; ++k) {
const x = i + dirs[k];
const y = j + dirs[k + 1];
if (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;
}(code-box)
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
}
}(code-box)
public class Solution {
public int NumIslands(char[][] grid) {
int m = grid.Length;
int n = grid[0].Length;
int ans = 0;
int[] dirs = { -1, 0, 1, 0, -1 };
void Dfs(int i, int j) {
grid[i][j] = '0';
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);
}
}
}
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;
}
}(code-box)
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 × n), and the space complexity is O(m × n). Where m and n are the number of rows and columns in the grid, respectively.
PythonJavaC++GoTypeScriptRust
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(code-box)
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';
}
}
}
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
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;
}(code-box)
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
}
}(code-box)
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 × n × log (m × n)), and the space complexity is O(m × n). Where m and n are the number of rows and columns in the grid, respectively.
PythonJavaC++GoTypeScriptRust
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)
)(code-box)
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];
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
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;
}(code-box)
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
}
}(code-box)
