CODEWITHSUNDEEP
pythonlist
user18083034
user18083034

Reputation: 19

Finding neighbours in a list -Python

How to find the difference between neighboring numbers in a list whose difference is 1 and print the length of the longest series of neighbours within the list.

For example, in the list

[1, 2, 5, 4, 3, 4] the longest list of neighbours would be

[5, 4, 3, 4], with a length of 4.

I am stuck at this point,

    a = [1, 2, 5, 7, 6, 5, 6, 3, 4, 1, 0]
    b = []
    for i in range(len(a)-1):
        c = (abs(a[i] - a[i+1]))
        if c == 1:
            print(a[i])

Upvotes: 0

Views: 4016

Answers (3)

ciayko
ciayko

Reputation: 19

#shorter, without temp list
def get_longest_sequence(my_list: list):
    longest = 1
    result = 1
    for i in range(1, len(my_list)):
        if abs(my_list[i-1]-my_list[i]) == 1:
            result += 1
        else:
            result = 1
        longest = max(longest, result)
    return longest

Upvotes: 2

BartoszKP
BartoszKP

Reputation: 35921

Usually when you want to find an extremum you hold two variables: current and best. In this case the best one is the longest sequence. So the most basic approach is to keep appending items to a list for as long as the property holds.

Let's try a naive solution: for each position in the list, calculate the longest sequence meeting the constraints:

def get_sequence(a, i):
    result = [a[i]]
    while i < len(a)-1 and abs(a[i] - a[i+1]) == 1:
        result.append(a[i+1])
        i += 1
    return result

a = [1, 2, 5, 4, 3, 4]
longest = []
for i in range(len(a)):
    current = get_sequence(a, i)
    if len(current)> len(longest):
        longest = list(current)

print(longest)

The problem with this solution is that its complexity is O(n^2). And we can see that we are unnecessarily evaluating some subsequences more than once. If we've already checked that [2,3,4] is the longest subsequence starting with "2", there is no point trying to start from "3", because we already know the element after "4" doesn't meet the constraints. So we can take advantage of this property to have a solution that has linear complexity:

def get_sequence(a, i):
    result = [a[i]]
    while i < len(a)-1 and abs(a[i] - a[i+1]) == 1:
        result.append(a[i+1])
        i += 1
    return result

a = [1, 2, 5, 4, 3, 4]
longest = []
i = 0
while i < len(a):
    current = get_sequence(a, i)
    if len(current)> len(longest):
        longest = list(current)
    i += len(current)

print(longest)

Another possible solution, closer to what you've got right now and also O(n):

longest = []
current = [a[0]]
for i in range(len(a)):
  c = (abs(a[i] - a[i+1])) if i < len(a)-1 else 0
  if c == 1:
    current.append(a[i+1])
  else:
    if len(current) > len(longest):
      longest = list(current)
    current = [a[i+1]] if i < len(a)-1 else []

print(longest)

Seems a bit kludgey because of the end-list edge conditions - probably could use some improvement.

Upvotes: 1

Anass
Anass

Reputation: 436

a = [1, 2, 5, 7, 6, 5, 6, 3, 4, 1, 0]
list_of_lengths = [] #to store the length of all series
k = 0 
old_series = False #to see if it's a new series or no
for i in range(len(a)-1):
    c = (abs(a[i] - a[i+1]))
    if c == 1 and old_series ==  False:
        k =1
        old_series = True
    if c == 1 and old_series :
        k+=1
    if c != 1 and old_series :
        list_of_lengths.append(k)
        k=0
        old_series = False

if k>0 and old_series: #in case the last element is also in the series
    list_of_lengths.append(k)   
print(max(list_of_lengths))

>>> 4

Upvotes: 0

Related Questions