How To Find The Longest Consecutive Chain Of Numbers In An Array

For example we have [0, 1, 3, 5, 7, 8, 9, 10, 12, 13] . The result must be 7, 8, 9, 10 because they are adjacent to each other, index wise and are consecutive integers, and also t

Solution 1:

Group the items into subsequences using itertools.groupby based on constant differences from an increasing count (provided by an itertools.count object), and then take the longest subsequence using the built-in max on key parameter len:

from itertools import groupby, count

lst = [0, 1, 3, 5, 7, 8, 9, 10, 12, 13]
c = count()
val = max((list(g) for _, g in groupby(lst, lambda x: x-next(c))), key=len)
print(val)
# [7, 8, 9, 10]

You may include the group key in the result (suppressed as _) to further understand how this works.

Solution 2:

Alternative solution using numpy module:

import numpy as np

nums = np.array([0, 1, 3, 5, 7, 8, 9, 10, 12, 13])
longest_seq = max(np.split(nums, np.where(np.diff(nums) != 1)[0]+1), key=len).tolist()    
print(longest_seq)

The output:

[7, 8, 9, 10]

---

• np.where(np.diff(nums) != 1)[0]+1 - gets the indices of elements on which the array should be split (if difference between 2 consequtive numbers is not equal to 1, e.g. 3 and 5)

• np.split(...) - split the array into sub-arrays

https://docs.scipy.org/doc/numpy-dev/reference/generated/numpy.diff.html#numpy.diffhttps://docs.scipy.org/doc/numpy-dev/reference/generated/numpy.split.html

Solution 3:

Code

Using itertools.groupby (similar to @Moses Koledoye's answer):

groups = [[y[1] for y in g] for k, g in itertools.groupby(enumerate(iterable), key=lambda x: x[0]-x[1])]
groups
# [[0, 1], [3], [5], [7, 8, 9, 10], [12, 13]]max(groups, key=len)
# [7, 8, 9, 10]

Alternative

Consider the third-party tool more_itertools.consecutive_groups:

import more_itertools as mit


iterable = [0, 1, 3, 5, 7, 8, 9, 10, 12, 13]
max((list(g) for g in mit.consecutive_groups(iterable)), key=len)
# [7, 8, 9, 10]