In this guide, you will get 200. Number of Islands LeetCode Solution with the best time and space complexity. The solution to Number of Islands problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] is '0' or '1'.
Complexity Analysis
Time Complexity: O(mn)
Space Complexity: O(\min(m, n))
200. Number of Islands LeetCode Solution in C++
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
const int m = grid.size();
const int n = grid[0].size();
int ans = 0;
auto bfs = [&](int r, int c) {
queue<pair<int, int>> q{{{r, c}}};
grid[r][c] = '2'; // Mark '2' as visited.
while (!q.empty()) {
const auto [i, j] = q.front();
q.pop();
for (const auto& [dx, dy] : dirs) {
const int x = i + dx;
const int y = j + dy;
if (x < 0 || x == m || y < 0 || y == n)
continue;
if (grid[x][y] != '1')
continue;
q.emplace(x, y);
grid[x][y] = '2'; // Mark '2' as visited.
}
}
};
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (grid[i][j] == '1') {
bfs(i, j);
++ans;
}
return ans;
}
}; /* code provided by PROGIEZ */
200. Number of Islands LeetCode Solution in Java
class Solution {
public int numIslands(char[][] grid) {
int ans = 0;
for (int i = 0; i < grid.length; ++i)
for (int j = 0; j < grid[0].length; ++j)
if (grid[i][j] == '1') {
bfs(grid, i, j);
++ans;
}
return ans;
}
private static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
private void bfs(char[][] grid, int r, int c) {
Queue<Pair<Integer, Integer>> q = new ArrayDeque<>(List.of(new Pair<>(r, c)));
grid[r][c] = '2'; // Mark '2' as visited.
while (!q.isEmpty()) {
final int i = q.peek().getKey();
final int j = q.poll().getValue();
for (int[] dir : dirs) {
final int x = i + dir[0];
final int y = j + dir[1];
if (x < 0 || x == grid.length || y < 0 || y == grid[0].length)
continue;
if (grid[x][y] != '1')
continue;
q.offer(new Pair<>(x, y));
grid[x][y] = '2'; // Mark '2' as visited.
}
}
}
} // code provided by PROGIEZ
200. Number of Islands LeetCode Solution in Python
class Solution:
def numIslands(self, grid: list[list[str]]) -> int:
dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
m = len(grid)
n = len(grid[0])
def bfs(r, c):
q = collections.deque([(r, c)])
grid[r][c] = '2' # Mark '2' as visited.
while q:
i, j = q.popleft()
for dx, dy in dirs:
x = i + dx
y = j + dy
if x < 0 or x == m or y < 0 or y == n:
continue
if grid[x][y] != '1':
continue
q.append((x, y))
grid[x][y] = '2' # Mark '2' as visited.
ans = 0
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
bfs(i, j)
ans += 1
return ans # code by PROGIEZ
