My O(n) C++ solution


  • 0
    N
    int numIslands(vector<vector<char>>& grid) {
        int num = 0;
        int index = 0;
        if(grid.size() == 0){
            return 0;
        }
        vector<int> prev = vector<int>(grid[0].size(), 0);
        vector<int> curr = vector<int>(grid[0].size(), 0);
        
        for(int i = 0; i < grid.size(); i++){
            for(int j = 0; j < grid[i].size(); j++){
                if(grid[i][j] == '0'){
                    curr[j] = 0;
                    continue;
                }else{
                    int up = prev[j];
                    int left = j > 0 ? curr[j - 1] : 0;
                    if(up == 0 && left == 0){
                        num++;
                        index++;
                        curr[j] = index;
                    }
                    if(up == 0 && left != 0){
                        curr[j] = left;
                    }
                    if(up != 0 && left == 0){
                        curr[j] = up;
                    }
                    if(up != 0 && left != 0){
                        curr[j] = up;
                        if(left != up){
                            for(int k = 0; k < grid[0].size(); k++){
                                curr[k] = (curr[k] == left) ? up : curr[k];
                            }
                            num--;
                        }
                    }
                }
            }
        }
        return num;
    }

Log in to reply
 

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