Sponsored
Sponsored
This approach uses Depth-First Search (DFS) to explore the grid. We iterate over each cell in the grid, and every time we find an unvisited '1', it indicates the discovery of a new island. We then perform DFS from that cell to mark all the connected '1's as visited, effectively marking the entire island.
Time Complexity: O(m*n) where m is the number of rows and n is the number of columns since each cell is visited once.
Space Complexity: O(m*n) in the worst case due to the recursion stack used by DFS.
1#include <vector>
2using namespace std;
3
4void dfs(vector<vector<char>>& grid, int r, int c) {
5 if (r < 0 || c < 0 || r >= grid.size() || c >= grid[0].size() || grid[r][c] == '0') {
6 return;
7 }
8 grid[r][c] = '0';
9 dfs(grid, r-1, c);
10 dfs(grid, r+1, c);
11 dfs(grid, r, c-1);
12 dfs(grid, r, c+1);
13}
14
15int numIslands(vector<vector<char>>& grid) {
16 int numIslands = 0;
17 for (int i = 0; i < grid.size(); i++) {
18 for (int j = 0; j < grid[0].size(); j++) {
19 if (grid[i][j] == '1') {
20 numIslands++;
21 dfs(grid, i, j);
22 }
23 }
24 }
25 return numIslands;
26}The DFS implementation in C++ uses a similar approach to the C version but takes advantage of C++'s STL vector. It iteratively runs DFS on unvisited '1's to mark them, effectively marking out distinct islands.
This approach uses Breadth-First Search (BFS) to traverse the grid. Similar to DFS, we treat each '1' as a node in a graph. On encountering a '1', we initiate a BFS to explore all connected '1's (island nodes) by utilizing a queue for the frontier, marking them in-place as visited.
Time Complexity: O(m*n), where m and n are rows and columns.#
Space Complexity: O(min(m, n)) due to the queue storage in BFS.
1
Java's solution leverages a Queue to implement BFS. When encountering '1', BFS starts and expands, visiting the whole component marking each cell and exploring adjacent '1's iteratively using the queue.