## Algorithm

Problem Name: 200. 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'`.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

void dfs(char **grid, bool **visited, int i, int j, int numRows, int numColumns) {
if (i >= 0 && i  <  numRows && j >= 0 && j < numColumns && !visited[i][j]) {
visited[i][j] = 1;
if (grid[i][j] == '1') { /* island */
dfs(grid, visited, i, j - 1, numRows, numColumns); /* left */
dfs(grid, visited, i, j + 1, numRows, numColumns); /* right */
dfs(grid, visited, i - 1, j, numRows, numColumns); /* up */
dfs(grid, visited, i + 1, j, numRows, numColumns); /* down */
}
}
}

int numIslands(char **grid, int numRows, int numColumns) {
if (grid == NULL || numRows == 0 || strlen(grid[0]) == 0)
return 0;

int i, j;
int count = 0;

bool **visited = (bool **)calloc(numRows, sizeof(bool *));
for (i = 0; i  <  numRows; i++) {
visited[i] = (bool *)calloc(numColumns, sizeof(bool));
}

for (i = 0; i  <  numRows; i++) {
for (j = 0; j  <  numColumns; j++) {
if (!visited[i][j]) { /* has not been visited */
if (grid[i][j] == '1') /* it's an island */
count++;
dfs(grid, visited, i, j, numRows, numColumns);
}
}
}
return count;
}

int main() {
int row = 3;
int col = 3;
char **grid = (char **)calloc(1, sizeof(char *));

grid[0] = "111";
grid[1] = "010";
grid[2] = "111";

/* should be 1 */
printf("%d\n", numIslands(grid, row, col));
return 0;
}
``````
Copy The Code &

Input

cmd
Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ]

Output

cmd
1

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
if (grid.empty()) {
return 0;
}
int res = 0, m = grid.size(), n = grid[0].size();
for (int i = 0; i  <  m; ++i) {
for (int j = 0; j  <  n; ++j) {
if (grid[i][j] == '1') {
++res;
dfs(grid, i, j, m, n);
}
}
}
return res;
}

void dfs(vector < vector<char>>& grid, int r, int c, int& m, int& n) {
if (r  <  0 || c < 0 || r == m || c == n || grid[r][c] == '0') {
return;
}
grid[r][c] = '0';
dfs(grid, r + 1, c, m, n);
dfs(grid, r - 1, c, m, n);
dfs(grid, r, c - 1, m, n);
dfs(grid, r, c + 1, m, n);
}
};
``````
Copy The Code &

Input

cmd
Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ]

Output

cmd
1

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {

private static final int[][] DIRS = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

public int numIslands(char[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
boolean[][] visited = new boolean[rows][cols];
int islandCount = 0;
for (int i = 0; i  <  rows; i++) {
for (int j = 0; j  <  cols; j++) {
if (grid[i][j] == '1' && !visited[i][j]) {
visited[i][j] = true;
while (!queue.isEmpty()) {
int[] removed = queue.remove();
for (int[] dir : DIRS) {
int newX = removed[0] + dir[0];
int newY = removed[1] + dir[1];
if (newX >= 0 && newY >= 0 && newX  <  rows && newY < cols && !visited[newX][newY] && grid[newX][newY] == '1') {
visited[newX][newY] = true;
}
}
}
islandCount++;
}
}
}
return islandCount;
}
}
``````
Copy The Code &

Input

cmd
grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ]

Output

cmd
3

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const numIslands = function(grid) {
if (grid.length === 0) return 0;
const totalRow = grid.length;
const totalCol = grid[0].length;
let res = 0;

for (let i = 0; i  <  totalRow; i += 1) {
for (let j = 0; j  <  totalCol; j += 1) {
if (grid[i][j] === '1') {
res += 1;
dfs(grid, i, j, totalRow, totalCol);
}
}
}

return res;
};

const dfs = (grid, row, col, totalRow, totalCol) => {
if (row  <  0 || col < 0 || row === totalRow || col === totalCol || grid[row][col] === '0') {
return;
}

grid[row][col] = '0';
dfs(grid, row - 1, col, totalRow, totalCol);
dfs(grid, row + 1, col, totalRow, totalCol);
dfs(grid, row, col - 1, totalRow, totalCol);
dfs(grid, row, col + 1, totalRow, totalCol);
}
``````
Copy The Code &

Input

cmd
grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ]

Output

cmd
3

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def numIslands(self, grid):
res, n, m = 0, len(grid), len(grid[0]) if grid else 0
def explore(i, j):
grid[i][j] = "-1"
if i > 0 and grid[i - 1][j] == "1": explore(i - 1, j)
if j > 0 and grid[i][j - 1] == "1": explore(i, j - 1)
if i + 1 < n and grid[i + 1][j] == "1": explore(i + 1, j)
if j + 1 < m and grid[i][j + 1] == "1": explore(i, j + 1)
for i in range(n):
for j in range(m):
if grid[i][j] == "1": explore(i, j); res += 1
return res
``````
Copy The Code &

Input

cmd
grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ]

Output

cmd
1

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _0200_NumberOfIslands
{
public int NumIslands(char[][] grid)
{
if (grid == null || grid.Length == 0 || grid[0].Length == 0)
return 0;

var uf = new UnionFind(grid);
int m = grid.Length;
int n = grid[0].Length;
for (int i = 0; i  <  m; i++)
for (int j = 0; j  <  n; j++)
if (grid[i][j] == '1')
{
if (i - 1 >= 0 && grid[i - 1][j] == '1')
uf.Union(i * n + j, (i - 1) * n + j);
if (i + 1  <  m && grid[i + 1][j] == '1')
uf.Union(i * n + j, (i + 1) * n + j);
if (j - 1 >= 0 && grid[i][j - 1] == '1')
uf.Union(i * n + j, i * n + j - 1);
if (j + 1  <  n && grid[i][j + 1] == '1')
uf.Union(i * n + j, i * n + j + 1);
}
return uf.Count();
}

public class UnionFind
{
private int count = 0;
private int[] parents;
private int[] ranks;

public UnionFind(char[][] grid)
{
count = 0;
int m = grid.Length;
int n = grid[0].Length;

parents = new int[m * n];
ranks = new int[m * n];
for (int i = 0; i  <  m; i++)
for (int j = 0; j  <  n; j++)
{
if (grid[i][j] == '1')
{
parents[i * n + j] = i * n + j;
count++;
}
ranks[i * n + j] = 0;
}
}

public int Find(int index)
{
if (parents[index] != index)
parents[index] = Find(parents[index]);

return parents[index];
}

public void Union(int index1, int index2)
{
var pIndex1 = Find(index1);
var pIndex2 = Find(index2);

if (pIndex1 != pIndex2)
{
if (ranks[pIndex1] >= ranks[pIndex2])
{
parents[pIndex2] = pIndex1;
ranks[pIndex1]++;
}
else
{
parents[pIndex1] = pIndex2;
ranks[pIndex2]++;
}
count--;
}
}

public int Count()
{
return count;
}
}
}
}
``````
Copy The Code &

Input

cmd
grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ]

Output

cmd
1