C++, 99ms, Simple Union Find Solution.


  • 0

    The intuitive idea is using union find to solve the question which has connections between each node and asking find how many separate parts. So for this question, each water could be a node, then at most, there could be m * n islands, each time we add a new position, we increase the number of islands, and check whether this newly added islands has connections with other previously added islands, if yes, we record those connections and using union find to check inner connection between other islands.

    
     vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
            vector<int> islands(m*n, 0);
            for(int i = 0;i < m * n;i++)
                islands[i] = i;
            vector<vector<int>> matrix(m,vector<int>(n,0));
            int count = 0; 
            int delta[] = {0,1,0,-1,0};
            vector<int> res;
            for(auto& pos : positions)
            {
                matrix[pos.first][pos.second] = 1;
                vector<pair<int,int>> connections;
                count++;
                for(int i = 0;i < 4;i++)
                {
                    int row = pos.first + delta[i];
                    int col = pos.second + delta[i+1];
                    if(row >= 0 && row < m && col >= 0 && col < n && matrix[row][col] == 1)
                    {
                        connections.push_back(make_pair((pos.first) * n + pos.second, (row)*n + col));
                    }
                }
                for(auto pai :connections)
                {
                    int left = pai.first;
                    int right = pai.second;
                    while(islands[left] != left)
                        left = islands[left];
                    while(islands[right] != right)
                        right = islands[right];
                    if(left != right)
                    {
                        count--;
                        islands[left] = right;
                    }
                }
                res.push_back(count);
            }
            return res; 
        }
    

Log in to reply
 

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