Leetcode Problem 128: Longest Consecutive Sequence

Problem description:

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.

Python solution Link to heading


# leetcode_128.py

class Solution:
    def longestConsecutive(self, nums: list[int]) -> int:
        if len(nums) == 0:
            return 0
        elif len(nums) == 1:
            return 1
        sorted_nums = sorted(set(nums))
        n = len(sorted_nums)
        count = 1
        max_count = 0
        for i in range(1, n):
            # if gap between current and previous element is greater than 1,
            # break current chain count, and check if it's greater than the
            # last recorded longest consecutive chain
            if sorted_nums[i] - sorted_nums[i - 1] > 1:
                if count > max_count:
                    max_count = count
                count = 0
            # otherwise just increase current chain count
            count += 1

        return max(max_count, count)

I wasn’t really confident in this solution, especially when handling edge cases like when the input array is made of all the same number, or with only one number, but it passes all test cases, so I’ll take it!

Python statistics Link to heading
Runtime: 473 ms - beats 50.44% of python3 submissions.
Memory Usage: 28.5 MB - beats 27.06% of python3 submissions.
Complexity analysis Link to heading

  • Time: $ O(n) $, because of the for loop and not because of sorted(), since it runs in $ O(n ~ log ~ n) $ and not $ O(n) $.

    In truth, I’m not too sure if the for loop is truly the most expensive operation, since it’s true that it runs $ n $ times but all the operations inside it run in $ O(1) $. From this point of view the most expensive operation would be the sorting, and thus overall runtime would be $ O(n ~ log ~ n) $.

  • Space: $ O(n) $ because we create a sorted list out of the input array. We could have $ O(1) $ if we sorted the array in place, but I try to avoid doing that if possible, as to keep input separated from data structures generated within the driver/solution code.



Share on:
LinkedIn