Python O(n) disjoint set


  • 0

    As I thought disjoint sets fit this problem perfectly, wanted to implement it for practice. Modified disjoint sets with path compression to get rid of ranks as a lower number has the higher rank by definition in this problem. Due to path compression and a pseudo rank system, time complexity will be O(n). Space complexity will be O(n) since we store a node, a parent pointer, and streak count for n elements (O(3n) = O(n))

        def longestConsecutive(self, nums):
            
            def get_parent(val, P):
                if P[val] == val: return val
                P[val] = get_parent(P[val], P)
                return P[val]
            
            def union(u, v, S, P):
                U, V = get_parent(u, P), get_parent(v, P)
                P[V], S[U] = P[U], S[U] + S[V]
                return S[U]
            
            if not nums: return 0
            S, P = {}, {}
            mx = 1
            for n in nums:
                if n not in P:
                    S[n], P[n] = 1, n
                    if n+1 in P: mx = max(mx, union(n, n+1, S, P))
                    if n-1 in P: mx = max(mx, union(n-1, n, S, P))
            return mx
    

Log in to reply
 

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