[Leetcode] Longest Consecutive Sequence

Problem

Given an unsorted array of integers, find the length of the longest consecutive elements sequence. Your algorithm should run in O(n) complexity. 

For example, given [100, 4, 200, 1, 3, 2], the longest consecutive elements sequence is [1, 2, 3, 4]. Therefore, return length = 4.

Algorithm

O(n*log(n))
Sort the array, then find the longest consecutive sequences in linear time.

O(n^2)

Build a set of numbers for O(1). Let L[i] = the length of the longest consecutive sequence containing  A[i]. We have following O(n^2) algorithm:

For i = 1:A.length

      cur = A[i]

      While(set.contains(cur--))

             L[i] = L[i]+1

     cur = A[i] + 1

     While(set.contains(cur++))
             L[i] = L[i]+1

    

     End

End

O(n)

Note, when A[i] and A[j] are in the same consecutive sequence, L[i] = L[j]. So, in the above algorithm, we have done repeated work. Once we computed the consecutive sequence, we visited all the elements in it. So, we can safely delete them from the set, without changing the result. By deleting the visited elements, we can reduce the running time to O(n). 

Code