Longest Consecutive Sequence

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Example 1:

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Constraints:

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

Solution

Get Nimmikrishnab’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

For each starting number, iterate through the sequence by checking the presence of consecutive numbers (n + 1, n + 2, etc.) in the set, counting their length. Update the longest sequence length at the end of iteration for each number in the input array.

# for each n in the given array:
# checks if n is the start of the sequence.
# if (n - 1) is present then the sequence would be (n - 1), n, (n + 1)...
# if (n - 1) is present then:
#  --> (n - 1) would have occurred before n and the sequence is counted already
#  --> (n - 1) will occur after n and the sequence would be covered then
# so just skip the iteration
# if (n - 1) is not present then means n could be the start of a sequence
# we will continously check from n, if (n + 1), (n + 2), (n + 3)... are present
# at the end of the while loop, update the longestlength before starting a new sequence for the next number in the array.

class Solution(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        numSet = set(nums) # to remove any duplicates
        longestlength = 0

        for n in nums:
            if (n - 1) not in numSet: 
                length = 0 
                while (n + length) in numSet:
                    length += 1

                longestlength = max(length, longestlength)
        return longestlength

while loop counts how many consecutive numbers starting from n exist in numSet. Increment length as long as (n + length) is found in the set.

After counting the length of the current sequence, compare it with longestlength and update if the current sequence is longer.

After iterating through all numbers, longestlength contains the length of the longest consecutive sequence, which is returned.

Time complexity: O(n)

Space complexity: O(n)