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.lengthn == grid[i].length1 <= m, n <= 300grid[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;
}
Input
Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output
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);
}
};
Input
Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output
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]) {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{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;
queue.add(new int[]{newX, newY});
}
}
}
islandCount++;
}
}
}
return islandCount;
}
}
Input
grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output
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);
}
Input
grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output
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
Input
grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output
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;
}
}
}
}
Input
grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output
1