How do you find the length of the longest consecutive sequence in an unsorted array in linear time?
You put the values into a set, and then you only start counting from the values that begin a sequence.
def longest_consecutive(nums):
values = set(nums)
best = 0
for value in values:
# Only start counting where a sequence really begins.
if value - 1 in values:
continue
length = 1
while value + length in values:
length += 1
if length > best:
best = length
return best
So how does it work? A value begins a sequence when the value before it is not in the set. So for every value in the set, you check whether the value before it is there, and if it is then this value is in the middle of a sequence and you skip it. If it is not there then you have found the start, and you walk forwards counting how long the sequence is.
And why is it linear? Because every value is walked only once. A value that is not a start is looked at once in the outer loop. A value that is in a sequence is counted once in the inner loop. So the total work is a small multiple of the number of values.
The next two questions in this topic look at the set and at the duplicates.