# Python O(n) disjoint set

• 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
``````

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