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


  • 0
    D

    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;
        }
    };

  • 0
    A

    DFS is not O(1) space.


Log in to reply
 

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