Very intuitive solution using Memoization and an optimised one accepted as best in C, both well-explained


  • 3

    We need to find all the isolated separate islands which means all the connected or adjacent are treated as single one.

    Using DFS or BFS in this case is quite instinctive to cover all the connected and then move to the next unlabelled so far

    So the first simple solution is to use an array -> bool *visited to record the states:

    • first initialise the states to be unvisited all of them
    • start the traversing from a '1' and unvisited cell and then move deeper until visited, or out of range or water '0';
    • then that's a independent island and we need to move further to find another '1' and unvisited cell and then again start the traversing till the last cell of the matrix; along the way, count the islands.

    Bang! End of Story!

    • space cost O(n*m)
    • time cost O(n*m) -> quite direct and clean.

    const int Directions[][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    bool inRange(int r, int c, int rSize, int cSize)
    {
        return r>=0 && r<rSize && c>=0 && c<cSize;
    }
    
    void traverse(int r, int c, int rSize, int cSize, char** grid, bool** visited)
    {
        if(!inRange(r, c, rSize, cSize)) return ;
        if(visited[r][c]) return ;
        if(grid[r][c] == '0') return ;
        visited[r][c] = 1;
        for(int i = 0; i < 4; i++)
        {
            int r0 = r+Directions[i][0];
            int c0 = c+Directions[i][1];
            traverse(r0, c0, rSize, cSize, grid, visited);
        }
    }
    //AC - 4ms;
    int numIslands(char** grid, int rSize, int cSize)
    {
        bool** visited = (bool**)malloc(sizeof(bool*)*rSize);
        for(int r = 0; r < rSize; r++)
        {
            visited[r] = (bool*)malloc(sizeof(bool)*cSize);
            memset(visited[r], 0, sizeof(bool)*cSize);
        }
        int count = 0;
        for(int r = 0; r < rSize; r++)
            for(int c = 0; c < cSize; c++)
            {
                if(grid[r][c]=='1' && !visited[r][c])
                {
                    traverse(r, c, rSize, cSize, grid, visited);
                    count++;
                }
            }
        return count;
    }
    

    The above solution is quite clean and easy already, but actually we can still do better:

    • since the problem does not prohibit us from modifying the grid matrix;
    • we can just use grid itself to label the state of the cell instead of another array;

    And now we does not need to maintain the states array -> initialisation, checking and modification, so the performance will be better now.

    Bang! End of Story!

    • space cost O(1)
    • time cost O(n*m)

    void traverse(int r, int c, int rSize, int cSize, char** grid)
    {
        grid[r][c] = '0';
        if(r>0 && grid[r-1][c]=='1')
            traverse(r-1, c, rSize, cSize, grid);
        if(c>0 && grid[r][c-1]=='1')
            traverse(r, c-1, rSize, cSize, grid);
        if(r<rSize-1 && grid[r+1][c]=='1')
            traverse(r+1, c, rSize, cSize, grid);
        if(r<cSize-1 && grid[r][c+1]=='1')
            traverse(r, c+1, rSize, cSize, grid);
    }
    
    //AC - 0ms;
    int numIslands(char** grid, int rSize, int cSize)
    {
        if(rSize==0 || cSize==0) return 0;
        int count = 0;
        for(int r = 0; r < rSize; r++)
            for(int c = 0; c < cSize; c++)
            {
                if(grid[r][c] == '1')
                {
                    count++;
                    traverse(r, c, rSize, cSize, grid);
                }
            }
    }

  • 0
    H

    second one, time cost is O(1) ?


  • 0

    Sorry, my bad input. I've updated it, thanks for your pointing it out.


Log in to reply
 

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