Longest continuous ranges in a list of integers

Presented with this convoluted description of a problem to solve, but simplified to a the following:

As in find_max_continuous_range([1, 1, 0, 6, 3, 5, 5, 4]) is the range [3,4,5,5,6] which gives you an answer of 5 since the other continuous range is [0, 1, 1] yielding a length of 3

Original description

Picking Tickets

Consider an array of n ticket prices, tickets. A number, m, is defined as the size of some subsequence of tickets, s, where each element
covers an unbroken range of integers. That is, if the elements in s are sorted, the absolute difference between any elements j and j + 1 is
either 0 or 1. Determine the maximum length of a subsequence chosen from the tickets array.

Example

tickets = [8, 5, 4, 8, 4]

Valid subsequences, sorted, are {4, 4, 5} and {8, 8}. These subsequences have m values of 3 and 2, respectively. Return 3.

Function Description

Complete the function maxTickets in the editor below.

maxTickets has the following parameter(s):

int tickets[n]: the ticket prices

Returns

int: the maximum possible value of m

Breakdown

• Separate all the numbers into buckets of the same value e.g. all number 2 go into bucket 2
• Then merge the continuous buckets as in if there are values for 1 and 2 merge buckets 1 and 2

Build the buckets

Here I am also capturing the minimum and maximum value encountered for an efficient scan model on large datasets

def build_ranges(input_numbers: list[int]) -> tuple[dict[int, int], int, int]:
    ranges = {}
    max_number = None
    min_number = None
    for number in input_numbers:
        if max_number is None or number > max_number:
            max_number = number
        if min_number is None or number <= min_number:
            min_number = number
        if number not in ranges:
            ranges[number] = [number]
        else:
            ranges[number].append(number)
    return ranges, max_number, min_number

Find the number ranges

This is to me the clearer and more concise version, but it depends on sorting the buckets in order. This operation sorted is optimized in the language

def number_ranges(input_numbers: list[int]) -> list[list[int]]:
    ranges, _, _ = build_ranges(input_numbers)
    outputs = []
    for current_key in sorted(ranges.keys()):
        values = ranges[current_key]
        if len(outputs) == 0:
            outputs.append(values)            
        elif outputs[-1][-1] + 1 == current_key:
            outputs[-1].extend(values)
        else:
            outputs.append(values)  
    return outputs

Also could do this

def number_ranges(input_numbers: list[int]) -> list[list[int]]:
    ranges, _, _ = build_ranges(input_numbers)
    outputs = []
    current_end = None
    for key, value in sorted(ranges.items(), key=lambda x: x[1]):
        if len(outputs) == 0:
            outputs.append(value)
            current_end = key + 1
            continue
        if key == current_end:
            outputs[-1].extend(value)
            current_end = key + 1
            continue
        outputs.append(value)
        current_end = key + 1
    return outputs

This is running the same merging of buckets without sorting the buckets, but utilizing the known min and max of the bucket values. Note you don't have to keep the values since the length is the desired end, but this is much easier to debug because you can check the last added output and pull the last int value added to find your current progress when merging ranges.

def number_ranges_less_ops(input_numbers: list[int]) -> list[list[int]]:
    ranges, max_number, min_number = build_ranges(input_numbers)
    outputs = []
    current_end = min_number
    while current_end <= max_number:
        values = ranges.get(current_end, [])
        if len(values) == 0:
            current_end += 1
            continue
        if len(outputs) == 0:
            outputs.append(values)
        elif outputs[-1][-1] + 1 == current_end:
            outputs[-1].extend(values)
        else:
            outputs.append(values)
        current_end += 1
    return outputs

Here is a utility method to compare the results of the two method range outputs

def compare_lists(first_items: list[list[int]], second_items: list[list[int]]) -> bool:
    matches = 0
    for a, b in itertools.zip_longest(first_items, second_items):
        if a is None or b is None:
            continue
        matches += all(x is not None and y is not None and x == y for x, y in itertools.zip_longest(a, b))
    return matches == len(first_items) == len(second_items)

and a random number generator with duplicates

def create_random_numbers(number_of_numbers: int) -> list[int]:
    return [random.randint(0, number_of_numbers) for _ in range(number_of_numbers)]

All together now

def main() -> None:
    inputs = [8, 4, 5, 4, 8]
    first_items = number_ranges(inputs)
    second_items = number_ranges_less_ops(inputs)
    ic(compare_lists(first_items, second_items))

    get_length = lambda x: len(x) if x is not None else 0
    sorted_items = sorted(second_items, key=get_length, reverse=True)
    ic(len(sorted_items[0]))

    large_inputs = create_random_numbers(5000)
    first_items = number_ranges(large_inputs)
    second_items = number_ranges_less_ops(large_inputs)
    ic(compare_lists(first_items, second_items))
    sorted_items = sorted(second_items, key=get_length, reverse=True)
    ic(len(sorted_items[0]))


if __name__ == "__main__":
    main()

Results

ic| compare_lists(first_items, second_items): True
ic| len(sorted_items[0]): 3
ic| compare_lists(first_items, second_items): True
ic| len(sorted_items[0]): 33