# C++ Union-Find amotrized O(n)

• ``````class Solution {
vector<int> id;
vector<int> size;
public:
int longestConsecutive(vector<int>& nums) {
int n = nums.size();
if(n < 2) return n;
size = vector<int>(n,1);
for(int i = 0; i < n; i++) {
id.push_back(i);
}
unordered_map<int,int> record;
for(int i = 0 ; i < n; i++) {
if(record.find(nums[i]) != record.end()) continue;
record[nums[i]] = i;
if(record.find(nums[i]-1) != record.end()) {
unionSet(i,record[nums[i]-1]);
}
if(record.find(nums[i]+1) != record.end()) {
unionSet(i,record[nums[i]+1]);
}
}
int res = *max_element(size.begin(),size.end());
return res;
}

int find(int p) {
while(p != id[p]) {
id[p] = id[id[p]];
p = id[p];
}
return p;
}
void unionSet(int a, int b) {
int i = find(a);
int j = find(b);
if(i == j) return;
if(size[i] > size[j]) {
id[j] = i;
size[i] += size[j];
} else {
id[i] = j;
size[j] += size[i];
}
}
};``````

• For those who are interested in union-find, here is a tutorial from Princeton U:

I have a similar solution in Java, runtime is 15 ms:

``````public class Solution {

private int n;
private int ids[];
private int sizes[];
private int maxSize;

public int longestConsecutive(int[] nums) {
if ((n = nums.length) == 0) return 0;
sizes = new int[n];
ids = new int[n];
Map<Integer, Integer> map = new HashMap<>();
Arrays.fill(sizes, 1);
maxSize = 1;
for (int i = 0; i < n; i++) {
if (map.containsKey(nums[i])) {
continue;
}
map.put(nums[i], i);
ids[i] = i;
if (map.containsKey(nums[i] - 1)) {
unite(i, map.get(nums[i] - 1));
}
if (map.containsKey(nums[i] + 1)) {
unite(i, map.get(nums[i] + 1));
}
}

return maxSize;
}

private void unite(int a, int b) {
int rootA = findRoot(a);
int rootB = findRoot(b);
if (rootA == rootB) {
return;
}
int small;
int large;
if (sizes[rootA] > sizes[rootB]) {
small = rootB;
large = rootA;
} else {
small = rootA;
large = rootB;
}
ids[small] = large;
sizes[large] += sizes[small];
if (sizes[large] > maxSize) {
maxSize = sizes[large];
}
}

private int findRoot(int i) {
while (i != ids[i]) {
ids[i] = ids[ids[i]];
i = ids[i];
}

return i;
}
}
``````

• Hi, I got accepted using similar idea

``````    unordered_map<int, int> m;

int findParent(int n){
while(m[n] != n)
n = m[n] = m[m[n]];
return n;
}

int longestConsecutive(vector<int>& nums) {
int r = 0;
for (int &i : nums) {
if (m[i]) continue;
m[i] = i;
if (m.find(i-1) != m.end())
m[i] = findParent(i-1);
if (m.find(i+1) != m.end())
m[i+1] = m[i];
}
for (int &i : nums)
r = max(r, i - findParent(i) + 1);
return r;
}
``````

At the first glance I was thinking this method should be O(nlogn), but it runs in 16ms, even better than my strict O(n) algo. Can anyone give me a rigious proof on its amortized complexity?

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