1

I have a sorted list of integers:

l = [1,2,4,5]

I want to find the next free number in that range, in this case 3.

Are there available Python functions that can help with this? To create this manually I was thinking I would need to fetch the first and last index from l and create a new list, l_all, of all sequential integers inbetween those two values. Then walk and compare both lists and when a number exists in l_all but does not exist in l I would have my next free number. I'm curious if there is a more Pythonic way of doing this.

David Buck
  • 3,752
  • 35
  • 31
  • 35
refriedjello
  • 657
  • 8
  • 18
  • "and create a new list l_all of all sequential integers in between those two values. " better yet, don't use a list, use a `range` object. That will be constant space, and constant time for checking if something exists in it. Anyway, your proposed solution seems fine to me. There is no built-in way to do this, as far as I am aware but maybe someone knows something – juanpa.arrivillaga Apr 28 '21 at 17:58

2 Answers2

2

The suggested duplicate appears to be looking for a single missing value, but your case asks for the first available integer.

This can be done in a single line without a loop:

l = [1,2,4,5]
min(set(range(1, max(l)+1)) - set(l))


3

This is performing a set difference between a set of all possible integers from 1 to the max value in your list, set(range(1, max(l)+1)), and the set of values in your list, set(l). Sets are unsorted by nature, so you can use the min of the resulting set to find the first missing integer.

One advantage of using sets over lists to find the missing values is that it will still work without sorting your initial list, whereas any method involving looping across values will require the initial list to be sorted.

Also FYI, set(a) - set(b) could also be written as set(a).difference(set(b)). Both are functionally equivalent.

David Buck
  • 3,752
  • 35
  • 31
  • 35
  • The first available one ***is*** the only one... In what way is that question different than the duplicate? – Tomerikoo Apr 28 '21 at 20:07
  • @Tomerikoo I'm going by the title of "Next available integer", not "Missing integer" which suggests a different approach from many of the answers on the dupe. I agree that in the toy example given, they are one and the same. – David Buck Apr 28 '21 at 20:10
  • Well feel free to edit the question to a more general form which is different than the dupe and I'll be happy to reopen :) – Tomerikoo Apr 28 '21 at 20:11
  • By the way, the second answer in that dupe is pretty similar to yours and finds ***all*** missing numbers (which can easily be modified to just take the first one...). Also [Jon's answer](https://stackoverflow.com/a/20718664/6045800) provide a similar solution. I think the dupe is justified on second thought... – Tomerikoo Apr 28 '21 at 20:14
  • I concede that there are solutions (although the second answer seems to unnecessarily wrap the range in a list comprehension) that could be used to resolve this question. – David Buck Apr 28 '21 at 20:36
  • @DavidBuck you shouldn't use a `set` here, use a `range` object. Something to the effect of `seq = range(1, max(l)+1)` Then `for x in l: if x not in seq: break` and `x` will be the number you need. This is actually as efficient as using a `set` since `range` objects have constant-time membership testing for integers. – juanpa.arrivillaga Apr 29 '21 at 09:12
1
for i in range(len(l)):
    a, b = i, i+1
    if b < len(l):
        if l[b] - l[a] > 1:
        print(l[a] + 1)
Dmitry Shevchenko
  • 468
  • 2
  • 13