40 lines concise and easy understand c++ solution, union find 1D

• ``````class Solution {
public:
vector<int> numIslands2(int m, int n, vector<pair<int, int>>& positions) {
vector<int> parent(m * n + 1, 0);
for(int i = 0; i < parent.size(); i++) parent[i] = i;
vector<int> result;
if(positions.size() == 0) return result;
unordered_set<int> isIsland;
vector<pair<int, int>> dir{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for(int i = 0; i < positions.size(); i++) {
isIsland.insert(positions[i].first * n + positions[i].second);
int res = i == 0 ? 1 : result.back() + 1;
for(int j = 0; j < 4; j++) {
int x = positions[i].first + dir[j].first;
int y = positions[i].second + dir[j].second;
if(x >= 0 && y >= 0 && x < m && y < n && isIsland.count(x * n + y)) {
int roota = find(parent, n, positions[i].first, positions[i].second);
int rootb = find(parent, n, x, y);
if(roota != rootb) {
unionset(parent, roota, rootb);
res--;
}
}
}
result.push_back(res);
}
return result;
}

int find(vector<int>& parent, int n, int x, int y) {
int i = x * n + y;
while(parent[i] != i) {
parent[i] = parent[parent[i]];
i = parent[i];
}
return i;
}

void unionset(vector<int>& parent, int roota, int rootb) {
parent[roota] = parent[rootb];
}
};
``````

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