My 25-line C++ Solution. Union Find.


  • 1
    F

    2228ms is not a fast solution but it is
    relatively short with about 25 lines.

    class Solution {
    public:
        vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
            // 2016-02-26 14:13:35 Zach
            unordered_map<int, int> hashmap;
            vector<int> result;
            int current = 0;
            for (auto position : positions) {
                set<int> parts;
                int orientation[][2] = {{0,1}, {0,-1}, {1, 0}, {-1, 0}};
                for (auto ori : orientation) {
                    int pos = (position.first + ori[0]) * (n + 2) + (position.second + ori[1]);
                    if (hashmap.find(pos) != hashmap.end()) {
                        while (hashmap[pos] != pos) pos = hashmap[pos];
                        parts.insert(pos);
                    }
                }
                current = current - parts.size() + 1;
                result.push_back(current);
                if (parts.size() == 0) {
                    hashmap[position.first * (n + 2) + position.second] = position.first * (n + 2) + position.second;
                } else {
                    hashmap[position.first * (n + 2) + position.second] = hashmap[*parts.begin()];
                    for(auto part : parts) {
                        hashmap[part] = hashmap[*parts.begin()];
                    }
                }
            }
            return result;
            // 2016-02-26 15:00:15 Finished.
        }
    };

Log in to reply
 

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