Longest consecutive sequence where each element is less than 3

Question

I've seen some longest consecutive sequence problems before such as find the increasing subsequence. I am now trying to further develop my skills. Given an array of integers, I want to find the longest consecutive sequence where the difference of all the elements in the respective subsequence is less than a given number, e.g. 3. An example is [10,11,12,15,13] where only the first three elements fulfill the condition. Also, I want to return the indexes of the first and last element from the given array.

I was thinking of making two functions; get_first_element(arr) and get_last_element(arr).

def get_last_ele(arr):
    longest_seq = 0
    last_ele = 0

    max_difference = 3

    for i in range (0, len(arr)):

        max_ele_seq = arr[i]
        min_ele_seq = arr[i]
        _count = 0
        _last_ele = i
        for j in range(i,len(arr)-i+1):
            ele_j = arr[j]
            if ele_j > max_ele_seq:
                max_ele_seq = ele_j
            if ele_j < min_ele_seq:
                min_ele_seq = ele_j
            if abs(max_ele_seq - min_ele_seq) > max_difference:
                break

            last_ele = j
            _count += 1

        if _count > longest_seq:
            longest_seq = _count
            last_ele = last_ele

    return last_ele

I feel like I can re-use this code to get the first element, but that will be redundant to have two similar functions. Is it possible to implement all of this in one function, and are there any better solutions with regards to time complexity?

Why is the inner loop for j in range(i,len(arr)-i+1): rather than for j in range(i,len(arr)):? — DarrylG
@DarrylG You are correct, not sure why I did that, maybe since I've seen similar things in the past. Removed it and got the correct output. The problem I'm having is, I feel like the code will be redundant if I make another function that returns the first element, just like with the def_get_last_ele(arr) function. Is there any easier way to implement a solution? — user11217408

Emma H Emma H · Accepted Answer · 2020-05-17T11:13:08

def get_longest_sequence(arr):
    """
    Prints out the longest sequence, its length, and the index of its first and last elements

    arr: list of numbers
"""

    longest_seq_length = 0
    last_ele_index_of_longest_seq = 0
    max_difference = 3

    for i in range(0, len(arr)): 

        max_ele_seq = arr[i]
        min_ele_seq = arr[i]

        count = 0

        for j in range(i, len(arr)):

            ele_j = arr[j]
            if ele_j > max_ele_seq:
                max_ele_seq = ele_j
            elif ele_j < min_ele_seq:
                min_ele_seq = ele_j

            if max_ele_seq - min_ele_seq > max_difference: # no need for abs() since max always larger than min
                break

            last_ele_index = j
            count += 1

        if count > longest_seq_length:
            longest_seq_length = count
            last_ele_index_of_longest_seq = last_ele_index
            # no need for last_ele = last_ele, it does nothing, merely reassigns itself

    longest_seq = arr[(last_ele_index_of_longest_seq - longest_seq_length + 1):(last_ele_index_of_longest_seq + 1)]
    print(f"The longest sequence found: {longest_seq}")
    print(f"Its length: {longest_seq_length}")
    print(f"Index of first element (with regards to arr): {last_ele_index_of_longest_seq - longest_seq_length + 1}")
    print(f"Index of last element: {last_ele_index_of_longest_seq}")

arr = [10,11,12,15,13]
get_longest_sequence(arr)

If you wanted to improve your coding further, maybe try editing the program such that it will print out all the longest sequences (i.e. if there were 2 different sequences, of the longest length, to print out both of them, rather than just the first one).

Longest consecutive sequence where each element is less than 3

1 Answers