CODEWITHSUNDEEP
pythonlist
henry
henry

Reputation: 965

Find longest consecutive range of numbers in list

I have the following list of numbers:

numbers = numbers = [  1, 3, 11,  12,  14,  15,  16, 3, 4, 6]

I would like to get the start and end index of the longest consecutive range of numbers. By consecutive range, I mean an integer range of number without skipping, i.e. 1,2,3,4,5...

This is how I have done it:

def get_longest_consecutive_numbers(numbers):

    # 1. Split the numbers list into sublists of consecutive numbers
    split_list = []
    j = 0
    for i in range(1,len(numbers)-1):
        if numbers[i]+1 is not numbers[i+1]:
            split_list.append(numbers[j:i])
            j = i

    # 2. Find index of longest sublist (of consecutive numbers)
    longest_sublist_index = max((len(l), i) for i, l in enumerate(split_list))[1]

    # 3. Concatenate all sublists up to this index back together
    rest = split_list[:longest_sublist_index]
    concat_list = [j for i in rest for j in i]

    # 4. 
    # Start Index: Length of concatenated list
    # End Index: Start Index + Length of longest sublist in split_list

    start_index = len(concat_list)
    end_index = start_index + len(split_list[longest_sublist_index])

    return start_index, end_index

If I apply my function to the list of numbers:

 get_longest_consecutive_numbers(numbers)

I get:

(3, 6)

which is correct... but...

I was wondering if there is a more straight-forward (better) way to do this ?

Upvotes: 0

Views: 2923

Answers (6)

memo
memo

Reputation: 1938

How about using a 2 pointer approach:

set start=0, end=0
set bestLen=1, bestStart=0

while end < len(numbers) - 1
    if numbers[end] + 1 == numbers[end + 1] then increase end; set bestLen = max(bestLen, end-start) (also set bestStart = start if you just updated bestLen)
    else increase end; set start = end

return the range [bestStart ... bestStart + bestLen]

You'll get O(n) time and O(1) extra space.

Upvotes: 1

Ayman_Negm
Ayman_Negm

Reputation: 21

@ncica 's answer will not work if the longest sequence goes till the last element of the given list. Because I have small reputation, I cannot comment on @ncica's answer and so I will write the code in this separate answer. It is a modified version of @ncica's answer that should work for this case as well:

def longest(numbers):
my_max, count_ = 1, 1
start_idx, end_idx = 0, 0
for i in range(len(numbers)-1):
    # if difference between number and his follower is 1,they are in sequence
    if numbers[i+1]-numbers[i] ==1:
        count_ = count_+1
    else:
        if count_ > my_max :
            my_max = count_
            end_idx = i
            start_idx = i+1 - my_max
        # Reset counter
        count_ = 1
if count_ > my_max:
    my_max = count_
    end_idx = i+1
    start_idx = i+2-my_max
return (start_idx,end_idx,my_max)

Upvotes: 1

Umesh
Umesh

Reputation: 971

You can also use recursion for it:

numbers = [1, 3, 11,  12,  14,  15,  16, 3, 4, 6]

def getMaxConsecutiveInd(index):
    if numbers[index] + 1 == numbers[index + 1]:
        # call the functions if values are cosecutive to check next value
        return getMaxConsecutiveInd(index + 1)
    # return last index for cosecutive numbers
    return index


max_length, start_index, end_index = 0,0,0

i = 0
while i < len(numbers) - 1:
    con_index = getMaxConsecutiveInd(i)
    # if available max_length is less than new_max_length(con_index - i)
    # then change start_index and end_index  
    if max_length < con_index - i:
        max_length = con_index - i
        start_index = i
        end_index = con_index
    # change value of i to latest con_index if i != con_index
    if i == con_index:
        i = i + 1
    else:
        i = con_index

print(start_index, end_index, max_length)
Output: (4,6,2)

numbers = [1, 2, 3, 4, 5, 6, 7, 11, 12, 14, 15, 16, 17, 18, 3, 4, 6]
Output: (0,6,6)

Upvotes: 2

ncica
ncica

Reputation: 7206

numbers = [  1, 3, 11,  12,  14,  15,  16, 3, 4, 6]

def longest(numbers):
    max, count_ = 1, 1
    start_idx, end_idx = 0, 0
    for i in range(len(numbers)-1):
        # if difference between number and his follower is 1,they are in sequence
        if numbers[i+1]-numbers[i] ==1:
            count_ = count_+1
        else:
            if count_ > max :
                max = count_
                end_idx = i
                start_idx = i+1 - max
            # Reset counter
            count_ = 1
    return (start_idx,end_idx,max)


print (longest(numbers))

output:

(4, 6, 3) #start_idx, end_idx, len

Upvotes: 2

pault
pault

Reputation: 43494

You can use numpy.diff to calculate the differences between successive elements in your list, and then use itertools.groupby to collect those elements with differences equal to 1.

import numpy as np
from itertools import groupby
from operator import itemgetter

def get_longest_consecutive_numbers(numbers):
    idx = max(
        (
            list(map(itemgetter(0), g)) 
            for i, g in groupby(enumerate(np.diff(numbers)==1), itemgetter(1)) 
            if i
        ), 
        key=len
    )
    return (idx[0], idx[-1]+1)

print(get_longest_consecutive_numbers(numbers))
#(4,6)

Upvotes: 1

Born Tbe Wasted
Born Tbe Wasted

Reputation: 610

Let's have a bit of fun :

  1. Create the range in which the list is included

  2. Symmetric difference of that with the list

  3. Compute the max distance between two following numbers (gives you the max length)

  4. Get the index of the start and end point

Here is the code :

def longest_weird(numbers):
    delta = list(set(range(max(numbers))).symmetric_difference(numbers))
    start,end = 0,0
    maxi = 0
    for i,x in enumerate(delta[:-1]):
        aux = max(maxi,delta[i+1]-x)
        if aux != maxi:
            start,end = (x+1,delta[i+1]-1)
            maxi = aux
    return numbers.index(start),numbers.index(end)

Upvotes: 1

Related Questions