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
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:
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.
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.