2
\$\begingroup\$

This is a Leetcode problem -

Given an unsorted array of integers, find the length of the longest consecutive elements' sequence.

Your algorithm should run in \$O(n)\$ complexity.

Example -

Input: [100, 4, 200, 1, 3, 2]
Output: 4

# Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Here is my solution to this challenge -

def longestConsecutive(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    if not nums:
        return 0

    nums = list(dict.fromkeys(nums))
    nums.sort()
    count = 1
    longest_streak = []

    for index, value in enumerate(nums):
        if index + 1 >= len(nums):
            break

        if nums[index + 1] == value + 1:
            count += 1
            longest_streak.append(count)
        else:
            count = 1

    if not longest_streak:
        return count

    return max(longest_streak)

Here is my Leetcode result -

enter image description here

So, I would like to know whether I could make this program faster and more efficient.

NOTE - Though my solution got accepted, I really have no idea about the time complexity of my program. Maybe someone could cover that too?

\$\endgroup\$
  • \$\begingroup\$ Isn't nums.sort() O(n*logn)? \$\endgroup\$ – a_faulty_star Jun 4 at 11:51
  • \$\begingroup\$ It is? Honestly, I don't really know why. Could you include this in an answer? \$\endgroup\$ – Justin Jun 4 at 13:38
  • 1
    \$\begingroup\$ @Justin It is, as Python uses the Timsort. \$\endgroup\$ – Peilonrayz Jun 4 at 15:50
  • \$\begingroup\$ @Justin you can just check the Solution that is provided here . It has a good explanation for three cases: O(n^2), O(n*logn) and O(n). Yours is the second one, and you can see how to do it in O(n) there. You can also check out the Discussions! \$\endgroup\$ – a_faulty_star Jun 7 at 5:43
  • 1
    \$\begingroup\$ Thanks, @a_faulty_star. I will definitely have a look. Seems like the best thing to do. Thanks again! \$\endgroup\$ – Justin Jun 7 at 8:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.