CODEWITHSUNDEEP
pythonpython-3.x
Csaba Dobo
Csaba Dobo

Reputation: 1

Python: find smallest missing positive integer in ordered list

I need to find the first missing number in a list. If there is no number missing, the next number should be the last +1.

It should first check to see if the first number is > 1, and if so then the new number should be 1.

Here is what I tried. The problem is here: if next_value - items > 1: results in an error because at the end and in the beginning I have a None. 

list = [1,2,5]
vlans3=list

for items in vlans3:
    if items in vlans3:

        index = vlans3.index(items)
        previous_value = vlans3[index-1] if index -1 > -1 else None
        next_value = vlans3[index+1] if index + 1 < len(vlans3) else None
        first = vlans3[0]
        last = vlans3[-1]

                #print ("index: ", index)
        print ("prev item:", previous_value)
        print ("-cur item:", items)
        print ("nxt item:", next_value)

        #print ("_free: ", _free)
        #print ("...")
        if next_value - items > 1:
            _free = previous_value + 1
            print ("free: ",_free)
            break

print ("**************")
print ("first item:", first)
print ("last item:", last)
print ("**************")

Another method:

L = vlans3

free = ([x + 1 for x, y in zip(L[:-1], L[1:]) if y - x > 1][0])

results in a correct number if there is a gap between the numbers, but if no space left error occurs: IndexError: list index out of range. However I need to specify somehow that if there is no free space it should give a new number (last +1). But with the below code it gives an error and I do not know why.

if free = []:
    print ("no free")
else:
    print ("free: ", free)

Upvotes: 0

Views: 1297

Answers (3)

alex
alex

Reputation: 11400

How about a numpy solution? Below code works if your input is a sorted integer list with non-duplicating positive values (or is empty).

nekomatic's solution is a bit faster for small inputs, but it's just a fraction of a second, doesn't really matter. However, it does not work for large inputs - e.g. list(range(1,100000)) completely freezes on list comprehension with inclusion check. Below code does not have this issue.

import numpy as np

def first_free_id(array):
    array = np.concatenate((np.array([-1, 0], dtype=np.int), np.array(array, dtype=np.int)))
    where_sequence_breaks = np.where(np.diff(array) > 1)[0]
    return where_sequence_breaks[0] if len(where_sequence_breaks)>0 else array[-1]+1
  1. Prepend the array with -1 and 0 so np.diff works for empty and 1-element lists without breaking existing sequence's continuity.
  2. Compute differences between consecutive values. Seeked discontinuity ("hole") is where the difference is bigger than 1.
  3. If there ary any "holes" return the id of the first one, otherwise return the integer succeeding the last element.

Upvotes: 0

nekomatic
nekomatic

Reputation: 6284

To get the smallest integer that is not a member of vlans3:

ints_list = range(min(vlans3), max(vlans3) + 1)
missing_list = [x for x in ints_list if x not in vlans3]
first_missing = min(missing_list)

However you want to return 1 if the smallest value in your list is greater than 1, and the last value + 1 if there are no missing values, so this becomes:

ints_list = [1] + list(range(min(vlan3), max(vlan3) + 2))
missing_list = [x for x in ints_list if x not in vlan3]
first_missing = min(missing_list)

Upvotes: 1

Seif
Seif

Reputation: 1097

First avoid using reserved word list for variable. Second use try:except to quickly and neatly avoid this kind of issues.

def free(l):
    if l == []: return 0
    if l[0] > 1: return 1
    if l[-1] - l[0] + 1 == len(l): return l[-1] + 1
    for i in range(len(l)):
        try:
            if l[i+1] - l[i] > 1: break
        except IndexError:
            break
    return l[i] + 1

Upvotes: 0

Related Questions