Leetcode - 128: Longest Consecutive Sequence
Given a list of numbers return length of longest consecutive elements
What's the question?
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
Let's look at an example
Input: nums = [100,4,200,1,3,2] Output: 4
The task is to solve the problem in
O(n) time. If this wasn't the constrain we could have sorted the list in
O(nlogn) time and checked for consecutive numbers with two
To achive that time complexity we will loop through the numbers and initialize a
length counter and check if
number + length is in the given
nums list. If it's there we will increase the
lenght counter by
We will keep on doing this unlit there is no number like
number + length available in the
Now we will take the
longest variable and update our
longest variable. The
longest variable will be initialized to
0 at start.
Show me the code
def longestConsecutive(nums): numsSet = set(nums) longest = 0 for number in nums: length = 0 while length + number in numsSet: length += 1 longest = max(longest, length) return longest
That's it for this blog, hope you found this helpful. You can connect with me on Twitter