[Union find] Is it okay?

I solved 128 Leetcode problem.

I have studied union-find as uf. Before I mention problem, uf is very funny algorithm. It treats relation and disjoint set which is two sets have not relations, but only it wants to know start and last. uf pursues result like developer.

We can use array, map to easily implement disjoint set and uf.

uf has 3 main apis

1. find
   • find root of input element
2. union
   • merge two group of dis joint set
3. connected
   • connectivity between two group of input elements.

each api’s time complexity gets \(O(\alpha(n) \approx O(1))\). in this context, \(\alpha(n)\) is inverse Ackermann function which is grows vey steadily.

let’s back to promblem.

Description is easy. find longest consecutive sequence. let’s assume there is input list with [100,2,200,3,4,1]. in this case, the longest consecutive sequcence is 1,2,3,4, so answer is 4.

this is my algorithm to use uf and map. I use map data structure to implement disjoint set with rank and union find.

start iteration from 0 index of list to last index, in each iteration, check value -1 and +1 to connect value and adjacent value. if they are conntected pass else union two disjoint set group. because of rank, union will join from small rank to big rank. lastly do iteration of rank in dis joint set, I get biggest one.

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        uf = uff(nums)

        for key in nums:
            key_m = key - 1
            key_p = key + 1
            if uf.find(key_m) != None:
                if uf.connected(key, key_m) == False:
                    uf.union(key, key_m)
                
            if uf.find(key_p) != None:
                if uf.connected(key, key_p) == False:
                    uf.union(key, key_p)
        
        subMax: int = 0
        for k, v in uf.rank.items():
            subMax = max(subMax, v)
        
        return subMax

let’s start to get time complexity of my algorithm.

1. iteration \(O(n)\)
2. uf is \(O(\alpha(n) \approx O(1))\) in each iteration result is \(O(n) \times O(1) = O(n)\)

even though I got \(O(n)\), my algorithm is the bottom 99% algorithm(very slow, almost 1 second). so I saw other, they also did implement by \(O(n)\), but don’t use uf.

first, we convert the list into a set to allow \(O(1)\), so takes \(O(n)\). second, for each iteration, check this value is possible to be smallest value in sequence by checking existance of value - 1, if value - 1 exists in list, if it doesn’t, entering inner loop to count how long then consecutive sequence continues by checking \(value + 1\), \(value + 2\) in the set, and track longest sequence value.

for v in nums:
    s.add(v) # s is set data structure.
sub_max = 0

for v in s:
    if v-1 not in s:
        length_longest = 1
        
        while v + leng_longest in s:
            
            length_longest += 1
        sub_max = max(sub_max, v + leng_longest)

return sub_max

this code also got \(O(n)\), but there is no boilerplate and optimized, this kind of algorithm’s real running time is under \(100ms\).

My algorithm is not okay...

• algorithm
• union-find