How do I find the largest range of integers in a array?

Question

I would like to write a function that takes in an array of integers and returns an array of length 2 that represents the largest range of integers contained in that array.

A range is defined as a set of consecutive numbers in the set of integers. For example, the output array [2, 6] represents the range {2, 3, 4, 5, 6}.

Assume non-empty arrays and one largest range only.

Sample Input: array[1, 11, 3, 0, 15, 5, 2, 4, 10, 7, 12, 6]

Sample Output: [0, 7]

The code below works for the example above but fails for the following input, for example: array[8, 4, 2, 10, 3, 6, 7, 9, 1] whose output should be [6, 10]. My code produces [1, 4]. Can someone help, please?

def largestRange(array):
    array.sort()
    initial = array[0]
    start_idx = initial
    final = initial
    last_idx = final
    length = 0
    size = (final - initial + 1)

    for i in range(1,len(array)):
        if array[i] - array[i-1] == 1 and i < len(array) - 1:
            final += 1
        elif array[i] - array[i-1] == 1 and i == len(array) - 1:
            final +=1
            if size > length:
                start_idx = initial
                last_idx = final
        else:
            if size > length:
                start_idx = initial
                last_idx = final
                length = size
            initial = array[i]
            final = initial

    return [start_idx, last_idx]

(The idea is to update the values of start_idx and last_idx everytime the sequence breaks and size > length)

Patrick Artner · Accepted Answer · 2022-04-30T11:30:43.377

You need to sort your data, then get what ranges are possible in the sorted data - then get the biggest range from it.

You should accumulate all found ranges and find the biggest one from it. Using your code:

def largestRange(array):
    array.sort()
    initial = array[0]
    last_idx = final
    size = (final - initial + 1)

    ran = []  # collect ranges
    for i in range(1,len(array)):
        if array[i] - array[i-1] == 1 and i < len(array) - 1:
            final += 1
        elif array[i] - array[i-1] == 1 and i == len(array) - 1:
            final += 1
            ran.append( (initial, final) )  # add range
        else:            
            ran.append( (initial, final) )  # add range
            initial = array[i]              # reset values
            final = initial                 # reset values

    # return the biggest found range
    return max(ran, key=lambda n: n[1]-n[0])
    

data = [8, 4, 2, 10, 3, 6, 7, 9, 1]
print(largestRange(data))

gives [6,10].

I asked I have a list of numbers that are sometimes consecutive - how to get a list of ranges from it? 2 days ago, using my proposed solution for that problem you can solve yours

def get_consecutive_ranges(numbers: list[int]):
    """Takes an input of integers in a list, yields the 
    ranges of consecutive numbers that form the list."""
    if not numbers:
        return []

    k = []
    start,stop = None,None
    for num in numbers:
        if stop is None:
            start, stop = num, num
        elif stop == num-1:
            stop += 1
        else:
            yield range(start,stop+1)
            start, stop = num, num

    yield range(start,stop+1)

data = [1, 11, 3, 0, 15, 5, 2, 4, 10, 7, 12, 6]
data.sort()

rg = get_consecutive_ranges(data)

# sort ranges by length ascending, take the last one
srg = sorted(rg, key=lambda g:len(g))[-1]
print([min(srg),max(srg))

to get to [0,7]. HTH.

Thanks for your solution. I have added a few extra lines of code because I was having issues with lists that contained duplicates or a single number, like, for example, ```array = list(dict.fromkeys(array))``` and an if statement, respectively. Cheers — Thadeu Freitas Filho, Apr 30 '22 at 23:41

How do I find the largest range of integers in a array?

1 Answers1