Problem Description
In "Longest Consecutive Sequence" we are given an unsorted array of integers, to find the length of the longest consecutive elements sequence.
For example, given [100, 4, 200, 1, 3, 2]
, the longest consecutive elements sequence is [1, 2, 3, 4]
. Return its length: 4
.
our algorithm should run in O(n)
complexity.
Solution
The first thing we need to do is to create a set from the given array. This will help us to check if a number is in the sequence or not in constant time.
We then iterate through the set and for each number, we check if its previous number is in the set. If it is not in the set, then we have found the start of a new sequence.
We then keep checking the next consecutive numbers until we find a number that is not in the set. We then update our maximum sequence length and continue with the next number in the set.
Here is the Python code for the solution:
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
num_set = set(nums)
max_len = 0
for num in num_set:
if num - 1 not in num_set:
curr_num = num
curr_len = 1
while curr_num + 1 in num_set:
curr_num += 1
curr_len += 1
max_len = max(max_len, curr_len)
return max_len
Complexity Analysis
The time complexity of this algorithm is O(n)
because we iterate through the set only once, and each set lookup and insertion takes constant time.
The space complexity is also O(n)
because we create a set from the given array.
Conclusion
In this post, we have learned how to solve the Longest Consecutive Sequence problem in Python. We used a set to keep track of the numbers in the sequence and iterated through the set to find the longest sequence. Happy coding! 😎