algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

longest-consecutive-sequence.py (859B)

      1 class Solution:
      2 
      3     def search(self, current, count):
      4         if not current in self.num_set:
      5             return count
      6         return self.search(current + 1, count + 1)
      7 
      8     def longestConsecutive(self, nums: List[int]) -> int:
      9         # idea:
     10             # this must be in linear time
     11             # this means we can't sort
     12             # we can use hashmaps though
     13                 # with this we could do some sort of key based increment checking, sorta like open addressing
     14                     # we'd evict elements as we go so we could achieve O(n)
     15             
     16             max_val = 0
     17             self.num_set = set(nums)
     18 
     19             for ele in self.num_set:
     20                 if ele - 1 in self.num_set:
     21                     continue
     22                 current = self.search(ele, 0)
     23                 max_val = max(current,max_val)
     24             return max_val