# My simple answer in Python. Real O(n).

• ``````class Solution(object):
def longestConsecutive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
dictionary = {}
maxLength = 1
for n in nums:
length = 1
left = 0
right = 0
if n in dictionary:
continue
dictionary[n] = 1
if n - 1 in dictionary:
length += dictionary[n - 1]
left = dictionary[n - 1]
if n + 1 in dictionary:
length += dictionary[n + 1]
right = dictionary[n + 1]
dictionary[n - left] = length
dictionary[n + right] = length
if maxLength < length:
maxLength = length
return maxLength``````

• Cannot understand. Can you write some comments? thanks!

• Maybe i cann't describle it correctly and resonably

dictionary = {} dictionary[x] = y means : the length 'y' of the longest consecutive sequence which contains the current element 'x'.
every time in the for circle， we find an element which has not been visited . Then we calculate and update the maxlenth the element can constructe.

• why the complicity is O(n)?
i in dict is O(n)
O(n^2) to the whole process

• @weiheng4
It's the complexity of a single dict lookup, which is on average O(1) and at worst O(n). .list() will always be O(n). wiki.python.org/moin/TimeComplexity

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.