# (Leetcode) Longest consecutive sequence in Python

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 -

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?

• Isn't nums.sort() O(n*logn)? – a_faulty_star Jun 4 '19 at 11:51
• It is? Honestly, I don't really know why. Could you include this in an answer? – Justin Jun 4 '19 at 13:38
• @Justin It is, as Python uses the Timsort. – Peilonrayz Jun 4 '19 at 15:50
• @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! – a_faulty_star Jun 7 '19 at 5:43
• Thanks, @a_faulty_star. I will definitely have a look. Seems like the best thing to do. Thanks again! – Justin Jun 7 '19 at 8:27