# My C++ code (8ms) O(mn) time O(1) space

• The basic idea is to do DFS to mark all "1"s in a island to avoid double counting.

``````class Solution {
public:
void DFS(vector<vector<char>> &grid, int i, int j, int row, int col)
{
grid[i][j] = 'w'; // mark as "w" to indicate it has been visited.
if(i>0 && grid[i-1][j]=='1') DFS(grid, i-1, j, row, col);
if(i<(row-1) && grid[i+1][j]=='1') DFS(grid, i+1, j, row, col);
if(j>0 && grid[i][j-1]=='1') DFS(grid, i, j-1, row, col);
if(j<(col-1) && grid[i][j+1]=='1') DFS(grid, i, j+1, row, col);
}

int numIslands(vector<vector<char>> &grid) {
int row = grid.size();
if(row == 0) return 0;
int col = grid[0].size();
if(col == 0) return 0;

int i, j, res=0;

for(i=0; i<row;i++)
{
for(j=0; j<col;j++)
{
if(grid[i][j]=='1')
{
res++; // new island, increase the counter
DFS(grid, i, j, row, col); // mark all "1" in this new island
}
}
}
//recover the grid
for(i=0; i<row;i++)
{
for(j=0; j<col;j++)
{
if(grid[i][j]=='w')
grid[i][j] = '1';
}
}
return res;
}
};``````

• DFS is not O(1) space.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.