Friedrich Ewald My Personal Website

Leetcode: Longest Consecutive Sequence

From an unsorted array nums, return the length of the longest consecutive sequence of numbers as an integer. For example, the list [100, 4, 200, 1, 3, 2] would return 4, because the longest consecutive sequence is [1, 2, 3, 4] with a length of 4. The algorithm should perform in O(n). Not mentioned in the task is that there can be duplicates of numbers. They should be ignored. The main problem when developing this algorithm is for it to perform it in O(n). A brute force method is quite easy and works for smaller lists. The pseudo code looks like this: 

for every element in list
  while next element in list
    take next element
    increment counter by 1
  endwhile
  return longest counter
endfor
This approach works but is very time consuming with a complexity of O(n^2). This is because for every element in the list we need to possibly visit every other element in the list. A possible solution is listed below. We need to convert the list into a set for faster access O(1). Then iterate over every number O(n). If the number is the smallest number in chain, we count up until we reach the end of the chain. With this approach we visit every number in the for loop exactly once and get a total time complexity of O(2n) -> O(n). The code below shows this algorithm. 
from typing import List, Optional

class Solution:
  def longestConsecutive(self, nums: List[int]) -> int:
    # Copy all numbers to a set for O(1) access.
    m = set()
    longest = 0
    for n in nums:
      m.add(n)

    for n in m:
      # Only iterate if the element is the smallest of the particular chain
      if n - 1 not in m:
        # Initialize counter
        current = 0
        while n + current in m:
          current += 1
        longest = max(longest, current)

    return longest


if __name__ == '__main__':
  s = Solution().longestConsecutive
  print(s([100,4, 200, 1, 3, 2]), 4)  # [1, 2, 3, 4]
  print(s([1]), 1)
  print(s([]), 0)
  print(s([1,2,3,4]), 4)
  print(s([1,2,3,4,6,7,5]), 7)
  print(s([4,3,2,1]), 4)
  print(s([3,4,1,2]), 4)
  print(s([0,3,7,2,5,8,4,6,0,1]), 9)
Runtime: 632 ms, faster than 50.27% of Python3 online submissions for Longest Consecutive Sequence. Memory Usage: 28.9 MB, less than 39.00% of Python3 online submissions for Longest Consecutive Sequence.

About the author

is an experienced Software Engineer with a Master's degree in Computer Science. He started this website in late 2015, mostly as a digital business card. He is interested in Go, Python, Ruby, SQL- and NoSQL-databases, machine learning and AI and is experienced in building scalable, distributed systems and micro-services at multiple larger and smaller companies.

Related Posts