# Longest Consecutive Sequence

## Description

Given a list of positive integers, write the shortest code to find the number count of the longest consecutive sequence of numbers within the list.

## Input

A list of positive integers. You can assume the list is not empty and may contain duplicates.

## Output

The length of the longest consecutive sequence of numbers within the list.

## Test cases

Input: [100, 4, 200, 1, 3, 2]
Output: 4 // because of [1, 2, 3, 4]

Input: [1, 2, 3, 4, 5]
Output: 5 // because of [1, 2, 3, 4, 5]

Input: [10, 9, 8, 7, 6, 5]
Output: 6 // because of [5, 6, 7, 8, 9, 10]

Input: [1, 1, 1, 2, 3]
Output: 3 // because of [1, 2, 3].

Input: 
Output: 1 // No consecutive numbers exist. You can leave the Output empty too or output -1. It must be shown by this no consecutive numbers exist

Input: [7, 3, 9, 5, 4, 2, 8]
Output: 4 // because of [2, 3, 4, 5].


Code with shortest bytes win, and if equated, the earlier post wins.

• 'none' could also be '1', right? forcing it to be 'none' seems to me to create an awkward edge-case that may often cost more to fix than the rest of the problem... Sep 10 at 18:14
• @DominicvanEssen you are potentially correct but by definition a consecutive number is one which has a number next to it. So there must be atleast 2 consecutive numbers. Regardless, I am removing that condition :,) Sep 10 at 18:17
• Suggest test case [1,2,3,4,2,2,2] (prevents simply sorting, taking differences, and counting runs of 1s). Sep 10 at 18:47
• A couple of edge cases that might trip up some approaches that may be worth adding - [3, 5, 7, 9, 11] (all step sizes equal) and [7, 7, 6, 6, 5, 5] (multiple repeats in the longest consecutive sequence). Sep 10 at 22:43

# Jelly, 6 bytes

f‘$ƬL’  Try it online!  Ƭ -- iterate until the result doesn't change, collecting intermediate value f‘ -- keep the values that are still in the list when each value is incremented L -- take the length (number of intermediate values, including the initial list and the empty list at the end) ‘ -- decrement  • V nice approach. Sep 10 at 23:11 # Jelly, 5 bytes ṬŒg§Ṁ  A monadic Link that accepts a list of positive integers and yields the length of the longest consecutive sequence. Try it online! ### How? ṬŒg§Ṁ - Link: list of positive integers, A e.g. [4, 8, 3, 4, 2, 7, 4] Ṭ - untruth {A} [0, 1, 1, 1, 0, 0, 1, 1] ( i.e.: 2 3 4 7 8 ) Œg - group runs of equal elements [, [1, 1, 1], [0, 0], [1, 1]] § - sums [0, 3, 0, 2] Ṁ - maximum 3  # Haskell, 32 bytes f[]=0 f l=1+f[n|n<-l,elem(n+1)l]  Try it online! Repeatedly filters l by only keeping elements n where n+1 is also in l, and counts how many repetitions until the list is empty. # Python 3, 45 bytes f=lambda l:len(l)and-~f({*l}&{x-1for x in l})  Try it online! Without using sets: Python, 48 bytes f=lambda l:l>[]and-~f([x for x in l if-~x in l])  Try it online! Repeatedly filters l by only keeping elements x where x+1 is also in l, and counts how many repetitions until the list is empty. # Vyxal, 35 bitsv2, 4.375 bytes ÞǔĠṠG  Try it Online! ### How? Port of my Jelly answer. ÞǔĠṠG - list of positive integers e.g. [4, 8, 3, 4, 2, 7, 4] Þǔ - unthruth [0, 1, 1, 1, 0, 0, 1, 1] ( i.e.: 2 3 4 7 8 ) Ġ - group runs of equal elements [, [1, 1, 1], [0, 0], [1, 1]] Ṡ - sums [0, 3, 0, 2] G - maximum 3  # J, 22 bytes [:#[:+/ .*~^:a:~1=-//~  Attempt This Online! We view this is a graph problem. Let's consider the example 10, 9, 8, 7, 6, 5 for the explanation: • 1=-//~ Create an adjacency matrix, where two numbers are connected if their difference is 1 (signs matter): 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0  This says that 10 connects to 9, 9 connects to 8, etc. • [:+/ .*~^:a: Multiply this matrix by itself until we reach a fixed point. One self-multiplication, eg, tells us the connections after two steps: 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0  After two steps, 10 connects to 8, 9 to 7, etc. Then two self multiplications show us the connections after 3 steps, and so on. Eventually, we'll reach a matrix of all zeroes and stop, and the length of this chain tells us the length of the longest consecutive run of numbers. • [:# So we return that length. ## J, port of ovs's answer, 21 20 bytes 1#@}.((e.>:)#[)^:a:~  Attempt This Online! • I really like the mathematical application and would definitively not have thought about the problem this way. Sep 12 at 12:44 # R, 5038 37 bytes Edit: -1 bytes thanks to Giuseppe \(x,y=rle(1:max(x)%in%x))max(y$l*y$v)  Attempt This Online! • max(y$l*y$v) is a byte shorter. Sep 11 at 15:29 • @Giuseppe - Thanks! Sep 11 at 16:10 # Scala 3, 7473 70 bytes Port of @xnor's Python answer in Scala. Thanks to @corvus_192's comment and @Kjetil S's comment. def f(l:Seq[Int]):Int=if(l.size<1)0 else 1+f(l.filter(l contains _+1))  Attempt This Online! • Because you reference f, this is a snippet, not a function. You'd need to include the declaration of f to make this answer valid. But you can save some bytes by switching from match to if-else and using & instead of intersect. Sep 11 at 13:59 • 74 bytes scala def f(l:Seq[Int]):Int=if(l.size<1)0 else 1+f(l.filter(x=>l.contains(x+1)))  Attempt This Online! Sep 12 at 10:19 • One more with l.contains(x+1)l contains x+1 Sep 12 at 12:23 • ...and without parenthesis we can remove x=> and use l contains _+1 to get 70 bytes. Sep 12 at 17:01 # VyxalG, 56 bitsv2, 7 bytes ṗ's¯1=A;@  Try it Online! #### Explanation ṗ's¯1=A;@ '# Implicit input ṗ' ; '# Filter the powerset by: s¯ # Sort and get deltas 1=A # All equal to 1? @ # Length of each inner list # Take the maximum # Implicit output  # julia, 24 22 bytes Edit: 2-byte improvement due to MarcMush Same approach as most others here, counting how many times v can be intersected with v-1 before we get an empty list !v=v>[]&&!(v∩.~-v)+1  Attempt This Online! ### How? !v = v > [] && # return 0 if v == [] and terminate, otherwise proceed !(v ∩ .~ -v) + 1 # recurse on the intersection of v with v + 1 and add 1 to count recursion depth. Here, ~ is bitwise not, so ~(-k) == k-1 for signed integers.  • -2 bytes Sep 11 at 23:00 • Thanks! Very clever trick with ~- incrementing by 1. Sep 13 at 6:18 • ~- actually decrements, -~ would increment (but doesn't work as well with the dot) Sep 13 at 23:05 # Factor + math.extras, 51 bytes [ sort members [ - -1 = ] max-monotonic-count 1 + ]  Attempt This Online! Sort, uniquify, then count the longest run of two adjacent numbers differing by one. # Python, 12211310152 51 bytes Port of Arnaulds answer lambda a:max(map(g:=lambda v:v in a and-~g(v+1),a))  Attempt This Online! Previous Answer lambda a:max(len([*l])for b,l in groupby(r in a for r in range(max(a)+1))if b) from itertools import*  Attempt This Online! • 109 bytes – MTN Sep 10 at 18:31 • Thanks, but I found a bug where it can also return the longest run that is not contained on the list. It was easy to fix tho, basically just if b. Sep 10 at 18:44 • You can do and-~g(v+1) to save a byte. Sep 10 at 20:15 # Nekomata, 7 bytes ˡ{N→ᵈ:∩  Attempt This Online! A port of @ovs's Jelly answer. ˡ{N→ᵈ:∩ ˡ{ Loop until failure, and return the number of iterations N Check if the list is nonempty → Increment ᵈ:∩ Intersect with the input  # 05AB1E, 6 bytes ZLåγOà  Port of @JonathanAllan's Jelly answer, so make sure to upvote him as well! Explanation: Z # Push the maximum of the (implicit) input-list (without popping) L # Pop and push a list in the range [1,max] å # Check for each value whether it's in the input-list (1 if truthy; 0 if falsey) γ # Group adjacent equal bits together O # Sum each inner list à # Pop and push the maximum # (which is output implicitly as result)  Since I was curious: a port of @ovs' Jelly answer is 8 bytes instead: .ΓÐ<åÏ}g  Explanation: .Γ } # Continue until the list no longer changes, keeping all intermediate results # (excluding the initial value), using the (implicit) input-list Ð # Triplicate the current list < # Pop the top copy, and decrease all its values by 1 å # Pop it and another list, and check for each value-1 whether it's in thelist Ï # Pop both again, and keep all values at the truthy positions g # After the changes-loop: pop and push its length # (which is output implicitly as result)  # Nibbles, 5.5 5 bytes (10 nibbles) ,|.$&+~$ Attempt This Online! Port of ovs' Jelly answer. ,|.$&+~$# full program ,|.$&+~   # with implicit arg:
.          # iterate while unique
$# starting with input: +~$    #   add 1 to every element
&       #   intersection with original list
|            # now, filter this list-of-lists
$# to include only non-empty lists , # and return its length  # JavaScript (ES6), 51 bytes a=>Math.max(...a.map(g=v=>a.includes(v)&&1+g(v+1)))  Try it online! ### Commented a => // a[] = input array Math.max(... // return the maximum value in this: a.map(g = v => // for each value v in a[], // using a recursive callback function g: a.includes(v) && // if a[] includes v: 1 + // increment the final result g(v + 1) // and do a recursive call with v + 1 ) // end of map() ) // end of Math.max()  # JavaScript (ES6), 56 bytes This version was originally shorter (50 bytes), but invalid (as pointed out by Dominic van Essen). Now fixed at the cost of 6 bytes by adding p^v?...:0, which makes it uncompetitive. Expects an Uint32Array. a=>a.sort().map(p=v=>p^v?p+1^(p=v)?i=1:m+=++i>m:0,m=1)|m  Try it online! • [1,2,3,4,2,2,2] should output 4: the 50-byte version currently outputs 3. Sep 10 at 19:34 • @DominicvanEssen This method is indeed invalid. Thanks for reporting this. Sep 10 at 20:13 # Ruby, 48 47 bytes ->l{1.step.find{|z|l.all?{|x|[*x..x+z]-l!=[]}}}  Try it online! # Charcoal, 2319 13 bytes ＩＬ⌈⪪⭆⊕⌈θ¬№θι1  Try it online! Link is to verbose version of code. Explanation: Port of @JonathanAllan's Jelly answer, with the "untruth" replaced by a map over range using 0 for present and 1 for absent as this lets me split on 1s to find the longest run of 0s. (I can't split on 0s as this will fail if there are 10 of the same value in the list.)  θ Input list ⌈ Maximum ⊕ Incremented ⭆ Map over implicit range and join № Count of ι Current value θ In input list ¬ Logical Not ⪪ 1 Split on 1s ⌈ Take the longest run of 0s Ｌ Take the length Ｉ Cast to string Implicitly print  Previous 19-byte solution also works with negative integers: Ｉ⌈Ｅθ⌈Ｅθ∧¬⁻…·ιλθ⊕⁻λι  Try it online! Link is to verbose version of code. Explanation: Creates inclusive ranges between all pairs of input elements and outputs the length of the longest range that is a subset of the input.  θ Input array Ｅ Map over elements θ Input array Ｅ Map over elements …· Inclusive range from ι Outer value to λ Inner value ⁻ Remove elements found in θ Input array ¬ Is empty ∧ Logical And λ Inner value ⁻ Minus ι Outer value ⊕ Incremented ⌈ Take the maximum ⌈ Take the maximum Ｉ Cast to string Implicitly print  # Perl 5, 32 bytes sub f{@_?1+f(grep$_+1~~@_,@_):0}


Try it online!

Copied idea from others here. Return count of rounds of removal of ints n where n+1 dont exists before list is empty.

# Rust, 74 bytes

Try it online!

|a:&[u8]|(*a.iter().min().unwrap()..).take_while(|x|a.contains(x)).count()


Explanation:

let f = |a: &[u8]| {
// create an iterator starting from the least element
(*a.iter().min().unwrap()..)
// take item if in list, stopping at the first item not in list
.take_while(|x| a.contains(x))
// get total number of items taken
.count()
};

• Welcome to Code Golf, and nice answer! Sep 14 at 5:28

# T-SQL, 114 bytes

SELECT MAX(c)FROM(SELECT COUNT(b)c FROM(SELECT a*(a+1)/2-SUM(a)OVER(ORDER BY a)b FROM @t GROUP BY a)X GROUP BY b)Y

dbfiddle

DECLARE @t TABLE(i INT NOT NULL IDENTITY(1,1) --table with identity to emulate a 'list' (not counted in byte count)
, a INT NOT NULL);

INSERT INTO @t (a) --Assigning the 'list' values (not counted in byte count)
VALUES(100)
, (4)
, (200)
, (1)
, (3)
, (2);

SELECT MAX(c) --5. Determine the maximum count from the subquery
FROM(
SELECT COUNT(*)c --4. Count how many rows make up each group
FROM(
--After this query it is simply a matter of determining which value of b appears the most times, and how many times that is.
SELECT a*(a+1)/2-SUM(a) OVER(ORDER BY a)b /*2. Calculates the sum of values which are missing from the consecutive sequence
between 1 and a (both inclusive).
This utilises the default behaviour of the windowed function. This defaults to:
SUM(a) OVER(ORDER BY a ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW)
Which is far more descriptive, but too verbose for golf :).*/
FROM @t
GROUP BY a --1. Removes duplicate occurences of a, as this is just noise anyway...
)X --necessary alias
GROUP BY b -- 3. Group by b as these are the groups we want to know the size of
)Y --necessary alias


This algorithm does the following:

• Remove duplicate elements (essentially turn a list into a set)
• Order the elements
• Find all the consecutive sequences
• Prescribe a unique identifier for each consecutive sequence
• Get the count of elements in each distinct sequence (length of each sequence)
• Get the maximum count.

In my opinion the interesting part of this is prescribing the unique identifier. Let's generalise the problem, starting with an arbitrary subset of the natural numbers.

$$X \subseteq \mathbb N_{\ne 0}$$

Consider the following binary relation

$$R = \{(a, b): |a - b| \leq 1, (a, b) \in X \times X\}$$ R is the set of all ordered pairs which are no more than 1 distance apart. Here the distance is taxicab or L1 or whatever you want to call it.

It's fairly easy to see that R is symmetric, and reflexive, but NOT transitive.

Take the example $$X = \{1, 2, 3, 5, 6, 7, 8\}$$ $$(1, 2) \in R , (2, 3) \in R , (1, 3) \notin R$$

You can't have three distinct natural numbers all within a distance of 1 from eachother.

We need to extend the definition of R so that it is transitive. We need to find the transitive closure of R.

$$R^{+} = R \cup \{(a, c): (a, b) \in R \wedge (b, c) \in R\}$$

Now we have an equivalence relation, and it properly describes the equivalence classes that underly this problem. However we still need to determine a label for each of these equivalence classes. Normally the smallest positive representitve of each equivalence class is chosen. This would be  and  in the example above. But these are just labels, as long as they are unique they could be anything. Let's make a function that sufficiently labels an element's equivalence class.

$$Label(i) = \sum_{k=1}^{i} k - \sum_{j\in X \wedge j\leq i}{j}$$

We can replace the first sum with the equivalent expression $$\sum_{k=1}^{i} k = \frac{i(i + 1)}{2}$$

Thus, $$Label(i) = \frac{i(i + 1)}{2} - \sum_{j\in X \wedge j\leq i}{j}$$

Intuitively this is just the sum of everything 'missing' up to the current element.

$$Label(i) = \sum_{j \in \mathbb N_{\ne 0} \setminus X \wedge j \leq i} j$$

Now i am really interested, is there a generalisation of this? That is to say if we take the base relation R and redefined it:

$$R = \{(a, b): |a - b| \leq k, (a, b) \in X \times X\}, k \in \mathbb N_{\ne 0}$$

Would there be an equivalent intuitive 'label function' for any value of k?

• FROM @t can be shortened to FROM@t for a byte Sep 11 at 20:28
• Nice catch! Do you know the syntax for striking through the byte count? Or do I just edit the answer to 113 without striking through 114? Sep 12 at 0:48
• if I remember correctly <s>text</s> does strikethrough Sep 12 at 2:33
• Thanks for teaching me how to format the strike through. I've tried the FROM@t but I am getting invalid syntax. I suspect there are only certain characters that are allowed to touch the FROM. Seems that left parenthesis can touch the right of the FROM and vice versa. Not 100% on all the golf tricks for t-sql yet. Sep 12 at 8:39

# Retina 0.8.2, 51 bytes

$, \d+$*
D1+,
O1+
(\G1+, |1\1)+
$#1¶ O#^ 1G  Try it online! Link includes test cases. Explanation: $
,


Suffix a comma to the last entry too.

\d+
$*  Convert to unary. D1+,  Deduplicate. O1+  Sort ascending. (\G1+, |1\1)+$#1¶


Count consecutive sequences. The first alternation is only possible at the start of the match, while the second alternation is only possible on subsequent repetitions of the capture group.

O#^


Sort descending numerically.

1G


Take the first (i.e. largest).

# Excel, 65 bytes

=MAX(LEN(TEXTSPLIT(CONCAT(FREQUENCY(A1#,SEQUENCE(MAX(A1#)))),0)))


Input is spilled vertical array in A1#.

# C (clang 16), 93 bytes

Using C23 _BitInt(65536) as a clang extension in C89 for implicit int. Works for input integers in the range [0,65535], e.g. 16-bit unsigned (but it takes them as an array of int, with an int n length). It returns the count.

typedef _BitInt(1<<16)T;f(*p,n){T b=0;for(;n--;)b|=(T)1<<p[n];for(n=1;b&=b<<1;n++);return n;}


First loop: Add each input to a set implemented as a bitmap (bitset |= 1<<n). Second loop: treating that as a wide integer, count the longest run of set bit. (Shift and AND to remove the low bit from each run of bits, count iterations until the whole thing becomes zero.)

Godbolt including a test caller with the test cases from the question.

See Add two really big numbers re: _BitInt. Clang 16 supports very large widths: the current max is 8388608 bits for signed or unsigned, _BitInt(1<<23). So not enough to handle values up to INT_MAX, but we don't handle negative int values either.

And yes, shifting and ANDing a 64KiB bitmap as a wide integer takes a ridiculous amount of asm instructions since clang fully unrolls it. I used _BitInt(1<<8) while developing this to keep edit/compile/run cycles short. With 1<<16 width, clang16 -std=gnu89 -Os -Wall -Wno-implicit-int makes 24249 lines of asm for x86-64 (only a couple of them labels instead of instructions.) It also uses about 30472 + 128 (red zone) = 30600 bytes of stack space. (64Kib = 8KiB)

Ungolfed:

typedef _BitInt(1<<8) T;   // narrower for testing with small number inputs
/* int */ ungolfed(int *p, int n){
T bitset = 0;
for(;n--;){
bitset |= (T)1<<p[n];   // cast needed *before* the shift
}
int retval=1;            // reuse n for this in the golfed version
// https://stackoverflow.com/questions/3304705/finding-consecutive-bit-string-of-1-or-0
while(bitset &= bitset<<1){ // doesn't count the iteration that clears the last bit, hence retval=1 to start
retval++;
}
return retval;
}


With clang -fsanitize=undefined, it will reject out-of-bounds inputs, e.g. runtime error: shift exponent 200000 is too large for 65536-bit type 'T' (aka '_BitInt(65536)')

• (We could do the same thing in C++ with std::bitset<65536>; it has operator<<, operator&=, and bitset.any() fort the second loop, as well as bitset[p[n]=1 for the first. (The constructors want strings or arrays like 0,1,1,0, not bit indices, so we'd still need to loop unless we used std::set instead. Or std::sort and look for runs.) Also, I think this is the first answer in a language that needs an explicit loop to operate on all elements of an array or set. Sep 11 at 18:29

=sort(max(len(split(join(,frequency(A:A,sequence(9^4))),0))))

Put the input in cells A1:A and the formula in B1.

Uses frequency() like the Excel answer. Does not require CSE.

# Haskell + hgl, 19 bytes

l<ixe(fl~<(<P1)<fe)


Uses xnor's method.

## 20 bytes

Here's one that works online:

P1<l<ih eq1<δ<sr<nb


Attempt This Online!

### Explanation

• nb removes all duplicates from the list
• sr sorts the list
• δ gets the differences between consecutive elements
• ih eq1 gets the longest contiguous sublist of 1s
• l takes the length
• P1 adds 1

## Reflection

Some things can be improved:

• The glue in fl~<(<P1)<fe is too much, there should be some helper function that can reduce the amount of glue here.
• sr<nb could probably be a single function.

# Uiua, 12 bytes

/↥⍘⊚-⇡⧻.⊝⊏⍏.


Try it!

/↥⍘⊚-⇡⧻.⊝⊏⍏.
⊏⍏.  # sort
⊝     # deduplicate
⇡⧻.      # copy & make series of same length
-         # subtract
⍘⊚          # invert where
/↥            # maximum

• Subtract by range and inverted where are clever! I found a 9-byter using both of our approaches. Oct 12 at 23:14
• Make that 8. Oct 12 at 23:27
• @chunes - post it. Well done! Oct 13 at 6:07

# Uiua, 8 bytes

/↥⊜⧻.⍘⊚⊝


Try it!

Inspired by Dominic van Essen's Uiua answer.

/↥⊜⧻.⍘⊚⊝
⊝  # deduplicate
⍘⊚   # inverted where, i.e. how many times each element occurs
⊜⧻.     # lengths of contiguous equal elements
/↥        # maximum


# Uiua, 18 bytes

+1/↥⊜⧻.=1≡/-◫2⊝⊏⍏.


Try it!

+1/↥⊜⧻.=1≡/-◫2⊝⊏⍏.
⊏⍏.  # sort
⊝     # deduplicate
◫2      # windows of size two
≡/-        # difference of each window
=1           # change non-ones to zeros
⊜⧻.             # find length of each contiguous group of ones
/↥                # maximum
+1                  # plus one