Number of Islands
Problem Statement
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
Video Explanation
Java Code
class Solution {
int[][] directions = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
private void dfs(int row, int col, char[][] grid) {
if(row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] != '1') {
return;
}
grid[row][col] = '2';
for(int[] direction : directions) {
int new_row = row + direction[0];
int new_col = col + direction[1];
dfs(new_row, new_col, grid);
}
}
public int numIslands(char[][] grid) {
int count = 0;
for(int i = 0; i < grid.length; i++) {
for(int j = 0; j < grid[0].length; j++) {
if(grid[i][j] == '1') {
dfs(i, j, grid);
count += 1;
}
}
}
return count;
}
}
C++ Code
class Solution {
public:
vector<vector<int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
void dfs(int row, int col, vector<vector<char>>& grid) {
if (row < 0 || row >= grid.size() || col < 0 || col >= grid[0].size() || grid[row][col] != '1') {
return;
}
grid[row][col] = '2';
for (vector<int>& direction : directions) {
int new_row = row + direction[0];
int new_col = col + direction[1];
dfs(new_row, new_col, grid);
}
}
int numIslands(vector<vector<char>>& grid) {
int count = 0;
for (int i = 0; i < grid.size(); i++) {
for (int j = 0; j < grid[0].size(); j++) {
if (grid[i][j] == '1') {
dfs(i, j, grid);
count += 1;
}
}
}
return count;
}
};
Python Code
class Solution:
directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
def dfs(self, row, col, grid):
if row < 0 or row >= len(grid) or col < 0 or col >= len(grid[0]) or grid[row][col] != '1':
return
grid[row][col] = '2'
for direction in self.directions:
new_row, new_col = row + direction[0], col + direction[1]
self.dfs(new_row, new_col, grid)
def numIslands(self, grid):
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
self.dfs(i, j, grid)
count += 1
return count
Javascript Code
var numIslands = function(grid) {
const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
function dfs(row, col) {
if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] !== '1') {
return;
}
grid[row][col] = '2';
for (const direction of directions) {
const new_row = row + direction[0];
const new_col = col + direction[1];
dfs(new_row, new_col);
}
}
let count = 0;
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[0].length; j++) {
if (grid[i][j] === '1') {
dfs(i, j);
count += 1;
}
}
}
return count;
};
Go Code
package main
func numIslands(grid [][]byte) int {
directions := [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
var dfs func(row, col int)
dfs = func(row, col int) {
if row < 0 || row >= len(grid) || col < 0 || col >= len(grid[0]) || grid[row][col] != '1' {
return
}
grid[row][col] = '2'
for _, direction := range directions {
new_row, new_col := row+direction[0], col+direction[1]
dfs(new_row, new_col)
}
}
count := 0
for i := 0; i < len(grid); i++ {
for j := 0; j < len(grid[0]); j++ {
if grid[i][j] == '1' {
dfs(i, j)
count += 1
}
}
}
return count
}
Complexity Analysis
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the grid.
Space Complexity: O(m * n), where m is the number of rows and n is the number of columns in the grid.