longest-consecutive-sequence-v2.py (1330B)
1 class Node(): 2 def __init__(self,parent,num): 3 self.parent = parent 4 self.num = num 5 # only accurate for root of tree 6 self.size = 1 7 8 def find(a): 9 if a.parent is None: 10 return a 11 return find(a.parent) 12 13 def union(a,b): 14 if b is None: 15 return a.size 16 a_rep = find(a) 17 b_rep = find(b) 18 b_rep.parent = a_rep 19 a_rep.size += b_rep.size 20 return a_rep.size 21 22 class Solution: 23 def search(self, current, count): 24 if not current in self.num_set: 25 return count 26 return self.search(current + 1, count + 1) 27 28 def longestConsecutive(self, nums: List[int]) -> int: 29 # idea: 30 # this must be in linear time 31 # this means we can't sort 32 # we can use union find which has amortized constant time union and find ops 33 34 # how? 35 # make the set of our numbers into k disjoint trees 36 # try to union each number with num + 1 37 # return largest sized union 38 39 nodes = {x : Node(None,x) for x in nums} 40 41 # do unions 42 max_size = 0 43 44 for nd_num in nodes: 45 a = nodes.get(nd_num) 46 b = nodes.get(nd_num + 1) 47 un_size = union(a,b) 48 max_size = max(max_size, un_size) 49 50 return max_size