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.
Examples:
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: 3Solution in Python
o solve the problem of counting the number of islands in a 2D binary grid, we can use a Depth-First Search (DFS) approach. The idea is to traverse the grid, and whenever we encounter a ‘1’ (representing land), we initiate a DFS to mark all connected ‘1’s (forming an island) as visited by changing them to ‘0’. This way, we ensure that each island is counted only once.
Steps
- Initialize the Number of Islands: Start by setting a counter to zero to keep track of the number of islands.
- Traverse the Grid: Loop through each cell in the grid.
- DFS on Land: If a cell contains ‘1’, it indicates the start of a new island. Increment the island counter and perform a DFS to mark all connected land cells as visited.
- Marking Visited Cells: During the DFS, convert each visited ‘1’ to ‘0’ to avoid counting the same island multiple times.
- Return the Result: After traversing the entire grid, return the island counter.
Python
from typing import List
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
# Helper function for depth-first search (DFS)
def dfs(grid, i, j):
# Check for boundaries and whether the cell is water ('0')
if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == '0':
return
# Mark the cell as visited by setting it to '0'
grid[i][j] = '0'
# Perform DFS in all four directions (up, down, left, right)
dfs(grid, i + 1, j) # down
dfs(grid, i - 1, j) # up
dfs(grid, i, j + 1) # right
dfs(grid, i, j - 1) # left
# Initialize the number of islands
num_islands = 0
# Traverse the grid
for i in range(len(grid)):
for j in range(len(grid[0])):
# If a '1' is found, it's a new island
if grid[i][j] == '1':
num_islands += 1 # Increment island count
dfs(grid, i, j) # Perform DFS to mark the entire island
# Return the total number of islands
return num_islandsExplanation
- DFS Helper Function:
- The
dfsfunction is a recursive function that marks all the connected land cells (‘1’s) as visited by setting them to ‘0’. It recursively checks the four possible directions (up, down, left, right).
- The
- Checking Boundaries:
- Before performing the DFS, the function checks if the current cell is within the grid boundaries and whether it is a ‘1’. If it’s not, the DFS call returns immediately.
- Marking as Visited:
- When a ‘1’ is found, it is marked as ‘0’ to prevent revisiting the same island.
- Traversing the Grid:
- The main loop iterates through each cell of the grid. When a ‘1’ is found, it indicates the start of a new island. The island counter is incremented, and the DFS is initiated to mark all connected land cells.
- Returning the Number of Islands:
- After the entire grid is processed, the total count of islands is returned.
This solution efficiently counts the number of islands by using DFS to traverse and mark connected components in the grid. It runs in O(m * n) time complexity, where m is the number of rows and n is the number of columns in the grid.
Solution in Javascript
JavaScript
/**
* @param {character[][]} grid
* @return {number}
*/
var numIslands = function(grid) {
// Helper function for depth-first search (DFS)
function dfs(grid, i, j) {
// Check for boundaries and whether the cell is water ('0')
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] === '0') {
return;
}
// Mark the cell as visited by setting it to '0'
grid[i][j] = '0';
// Perform DFS in all four directions (up, down, left, right)
dfs(grid, i + 1, j); // down
dfs(grid, i - 1, j); // up
dfs(grid, i, j + 1); // right
dfs(grid, i, j - 1); // left
}
// Initialize the number of islands
let numIslands = 0;
// Traverse the grid
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[0].length; j++) {
// If a '1' is found, it's a new island
if (grid[i][j] === '1') {
numIslands += 1; // Increment island count
dfs(grid, i, j); // Perform DFS to mark the entire island
}
}
}
// Return the total number of islands
return numIslands;
};Solution in Java
Java
class Solution {
public int numIslands(char[][] grid) {
// If the grid is empty, return 0
if (grid == null || grid.length == 0) {
return 0;
}
int numIslands = 0; // Initialize the number of islands
// Traverse the grid
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
// If a '1' is found, it's a new island
if (grid[i][j] == '1') {
numIslands++; // Increment the island count
dfs(grid, i, j); // Perform DFS to mark the entire island
}
}
}
// Return the total number of islands
return numIslands;
}
// Helper function for depth-first search (DFS)
private void dfs(char[][] grid, int i, int j) {
// Check for boundaries and whether the cell is water ('0')
if (i < 0 || i >= grid.length || j < 0 || j >= grid[i].length || grid[i][j] == '0') {
return;
}
// Mark the cell as visited by setting it to '0'
grid[i][j] = '0';
// Perform DFS in all four directions (up, down, left, right)
dfs(grid, i + 1, j); // down
dfs(grid, i - 1, j); // up
dfs(grid, i, j + 1); // right
dfs(grid, i, j - 1); // left
}
}Solution in C#
C#
public class Solution {
public int NumIslands(char[][] grid) {
// If the grid is empty, return 0
if (grid == null || grid.Length == 0) {
return 0;
}
int numIslands = 0; // Initialize the number of islands
// Traverse the grid
for (int i = 0; i < grid.Length; i++) {
for (int j = 0; j < grid[i].Length; j++) {
// If a '1' is found, it's a new island
if (grid[i][j] == '1') {
numIslands++; // Increment the island count
DFS(grid, i, j); // Perform DFS to mark the entire island
}
}
}
// Return the total number of islands
return numIslands;
}
// Helper function for depth-first search (DFS)
private void DFS(char[][] grid, int i, int j) {
// Check for boundaries and whether the cell is water ('0')
if (i < 0 || i >= grid.Length || j < 0 || j >= grid[i].Length || grid[i][j] == '0') {
return;
}
// Mark the cell as visited by setting it to '0'
grid[i][j] = '0';
// Perform DFS in all four directions (up, down, left, right)
DFS(grid, i + 1, j); // down
DFS(grid, i - 1, j); // up
DFS(grid, i, j + 1); // right
DFS(grid, i, j - 1); // left
}
}