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