Leetcode - 128: Longest Consecutive Sequence

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 for loops.

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

We will keep on doing this unlit there is no number like number + length available in the nums list.

Now we will take the max of length and 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