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

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

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