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
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)