6. Find the Number of Islands
The problem can be found at the following link: Question Link
Problem Description
Given a grid of size n*m
(where n
is the number of rows and m
is the number of columns in the grid) consisting of '0'
s (Water) and '1'
s (Land), find the number of islands. An island is a group of connected '1'
s that are surrounded by water or the grid boundary. The connection can be vertical, horizontal, or diagonal.
Note:
Islands are connected in all 8 possible directions: left, right, up, down, and the 4 diagonal directions.
The entire grid is traversed, and the number of distinct islands is counted.
Example:
Input 1:
grid = [[0, 1],
[1, 0],
[1, 1],
[1, 0]]
Output 1: 1
Explanation: All land cells are connected to form a single island.
Input 2:
grid = [[0, 1, 1, 1, 0, 0, 0],
[0, 0, 1, 1, 0, 1, 0]]
Output 2: 2
Explanation:
There are two islands, one formed by the group of '1'
s in the first three columns and another formed by the group of '1'
s in the sixth column.
My Approach
Depth-First Search (DFS):
We treat the grid as a graph and explore all connected cells containing
'1'
using DFS.For each unvisited land cell, we perform a DFS to mark all connected land cells as visited. This entire DFS traversal is considered as one island.
Repeat the process for each unvisited land cell until all cells are checked.
Checking Boundaries:
The
isValid()
function ensures that the current cell lies within the grid boundaries and contains a'1'
before proceeding with DFS.
DFS Traversal:
For each unvisited land cell, mark it as visited by setting it to
'0'
. Then, explore all 8 neighboring cells (horizontal, vertical, diagonal). If a neighboring cell is also land, continue the DFS from that cell.
Time and Auxiliary Space Complexity
Expected Time Complexity: O(n*m), where
n
is the number of rows andm
is the number of columns in the grid. This is because we visit each cell once and traverse its neighbors.Expected Auxiliary Space Complexity: O(n*m), as the DFS call stack can grow up to the total number of cells in the grid in the worst case.
Code (C++)
class Solution {
public:
vector<int> dx = {-1, 0, 1, 0, 1, -1, -1, 1};
vector<int> dy = {0, -1, 0, 1, 1, 1, -1, -1};
bool isValid(int x, int y, int n, int m) {
return (x >= 0 && x < n && y >= 0 && y < m);
}
void dfs(int x, int y, vector<vector<char>>& grid, int n, int m) {
grid[x][y] = '0';
for (int k = 0; k < 8; k++) {
int newX = x + dx[k];
int newY = y + dy[k];
if (isValid(newX, newY, n, m) && grid[newX][newY] == '1') {
dfs(newX, newY, grid, n, m);
}
}
}
int numIslands(vector<vector<char>>& grid) {
int n = grid.size();
int m = grid[0].size();
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == '1') {
ans++;
dfs(i, j, grid, n, m);
}
}
}
return ans;
}
};
Code (Java)
class Solution {
private int[] dx = {-1, 0, 1, 0, 1, -1, -1, 1};
private int[] dy = {0, -1, 0, 1, 1, 1, -1, -1};
public int numIslands(char[][] grid) {
int n = grid.length;
int m = grid[0].length;
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (grid[i][j] == '1') {
ans++;
dfs(i, j, grid, n, m);
}
}
}
return ans;
}
private void dfs(int x, int y, char[][] grid, int n, int m) {
grid[x][y] = '0'; // Mark the current cell as visited
for (int k = 0; k < 8; k++) {
int newX = x + dx[k];
int newY = y + dy[k];
if (isValid(newX, newY, n, m) && grid[newX][newY] == '1') {
dfs(newX, newY, grid, n, m);
}
}
}
private boolean isValid(int x, int y, int n, int m) {
return (x >= 0 && x < n && y >= 0 && y < m);
}
}
Code (Python)
class Solution:
def numIslands(self, grid):
n = len(grid)
m = len(grid[0])
ans = 0
dx = [-1, 0, 1, 0, 1, -1, -1, 1]
dy = [0, -1, 0, 1, 1, 1, -1, -1]
def dfs(x, y):
grid[x][y] = 0
for k in range(8):
newX = x + dx[k]
newY = y + dy[k]
if is_valid(newX, newY) and grid[newX][newY] == 1:
dfs(newX, newY)
def is_valid(x, y):
return 0 <= x < n and 0 <= y < m
for i in range(n):
for j in range(m):
if grid[i][j] == 1:
ans += 1
dfs(i, j)
return ans
Contribution and Support
For discussions, questions, or doubts related to this solution, please visit my LinkedIn: Any Questions. Thank you for your input; together, we strive to create a space where learning is a collaborative endeavor.
β Star this repository if you find it helpful or intriguing! β
πVisitor Count
Last updated