Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2]
,
The longest consecutive elements sequence is [1, 2, 3, 4]
. Return its length: 4
.
Your algorithm should run in O(n) complexity.
Intuition
Because a sequence could start at any number in nums
, we can exhaust the
entire search space by building as long a sequence as possible from every
number.
Algorithm
The brute force algorithm does not do anything clever - it just considers
each number in nums
, attempting to count as high as possible from that
number using only numbers in nums
. After it counts too high (i.e.
currentNum
refers to a number that nums
does not contain), it records the
length of the sequence if it is larger than the current best. The algorithm
is necessarily optimal because it explores every possibility.
Complexity Analysis
Time complexity : .
The outer loop runs exactly times, and because currentNum
increments by 1 during each iteration of the while
loop, it runs in
time. Then, on each iteration of the while
loop, an
lookup in the array is performed. Therefore, this brute force algorithm
is really three nested loops, which compound multiplicatively to a
cubic runtime.
Space complexity : .
The brute force algorithm only allocates a handful of integers, so it uses constant additional space.
Intuition
If we can iterate over the numbers in ascending order, then it will be easy to find sequences of consecutive numbers. To do so, we can sort the array.
Algorithm
Before we do anything, we check for the base case input of the empty array.
The longest sequence in an empty array is, of course, 0, so we can simply
return that. For all other cases, we sort nums
and consider each number
after the first (because we need to compare each number to its previous
number). If the current number and the previous are equal, then our current
sequence is neither extended nor broken, so we simply move on to the next
number. If they are unequal, then we must check whether the current number
extends the sequence (i.e. nums[i] == nums[i-1] + 1
). If it does, then we
add to our current count and continue. Otherwise, the sequence is broken, so
we record our current sequence and reset it to 1 (to include the number that
broke the sequence). It is possible that the last element of nums
is part
of the longest sequence, so we return the maximum of the current sequence and
the longest one.
Here, an example array is sorted before the linear scan identifies all consecutive sequences. The longest sequence is colored in red.
Complexity Analysis
Time complexity : .
The main for
loop does constant work times, so the algorithm's time
complexity is dominated by the invocation of sort
, which will run in
time for any sensible implementation.
Space complexity : (or ).
For the implementations provided here, the space complexity is constant because we sort the input array in place. If we are not allowed to modify the input array, we must spend linear space to store a sorted copy.
Intuition
It turns out that our initial brute force solution was on the right track, but missing a few optimizations necessary to reach time complexity.
Algorithm
This optimized algorithm contains only two changes from the brute force
approach: the numbers are stored in a HashSet
(or Set
, in Python) to
allow lookups, and we only attempt to build sequences from numbers
that are not already part of a longer sequence. This is accomplished by first
ensuring that the number that would immediately precede the current number in
a sequence is not present, as that number would necessarily be part of a
longer sequence.
Complexity Analysis
Time complexity : .
Although the time complexity appears to be quadratic due to the while
loop nested within the for
loop, closer inspection reveals it to be
linear. Because the while
loop is reached only when currentNum
marks
the beginning of a sequence (i.e. currentNum-1
is not present in
nums
), the while
loop can only run for iterations throughout the
entire runtime of the algorithm. This means that despite looking like
complexity, the nested loops actually run in
time. All other computations occur in constant time, so the overall
runtime is linear.
Space complexity : .
In order to set up containment lookups, we allocate linear space
for a hash table to store the numbers in nums
. Other than that,
the space complexity is identical to that of the brute force solution.
Analysis written by: @emptyset