get next available integer using LINQ

Question

Say I have a list of integers:

List<int> myInts = new List<int>() {1,2,3,5,8,13,21};

I would like to get the next available integer, ordered by increasing integer. Not the last or highest one, but in this case the next integer that is not in this list. In this case the number is 4.

Is there a LINQ statement that would give me this? As in:

var nextAvailable = myInts.SomeCoolLinqMethod();

Edit: Crap. I said the answer should be 2 but I meant 4. I apologize for that!

For example: Imagine that you are responsible for handing out process IDs. You want to get the list of current process IDs, and issue a next one, but the next one should not just be the highest value plus one. Rather, it should be the next one available from an ordered list of process IDs. You could get the next available starting with the highest, it does not really matter.

Answer 1

I see a lot of answers that write a custom extension method, but it is possible to solve this problem with the standard linq extension methods and the static Enumerable class:

List<int> myInts = new List<int>() {1,2,3,5,8,13,21};

// This will set firstAvailable to 4.
int firstAvailable = Enumerable.Range(1, Int32.MaxValue).Except(myInts).First();

Answer 2

The answer provided by @Kevin has a undesirable performance profile. The logic will access the source sequence numerous times: once for the .Count call, once for the .FirstOrDefault call, and once for each .Contains call. If the IEnumerable<int> instance is a deferred sequence, such as the result of a .Select call, this will cause at least 2 calculations of the sequence, along with once for each number. Even if you pass a list to the method, it will potentially go through the entire list for each checked number. Imagine running it on the sequence { 1, 1000000 } and you can see how it would not perform well.

LINQ strives to iterate source sequences no more than once. This is possible in general and can have a big impact on the performance of your code. Below is an extension method which will iterate the sequence exactly once. It does so by looking for the difference between each successive pair, then adds 1 to the first lower number which is more than 1 away from the next number:

public static int? FirstMissing(this IEnumerable<int> numbers)
{
    int? priorNumber = null;

    foreach(var number in numbers.OrderBy(n => n))
    {
        var difference = number - priorNumber;

        if(difference != null && difference > 1)
        {
            return priorNumber + 1;
        }

        priorNumber = number;
    }

    return priorNumber == null ? (int?) null : priorNumber + 1;
}

Since this extension method can be called on any arbitrary sequence of integers, we make sure to order them before we iterate. We then calculate the difference between the current number and the prior number. If this is the first number in the list, priorNumber will be null and thus difference will be null. If this is not the first number in the list, we check to see if the difference from the prior number is exactly 1. If not, we know there is a gap and we can add 1 to the prior number.

You can adjust the return statement to handle sequences with 0 or 1 items as you see fit; I chose to return null for empty sequences and n + 1 for the sequence { n }.

Answer 3

This will be fairly efficient:

static int Next(this IEnumerable<int> source)
{
    int? last = null;
    foreach (var next in source.OrderBy(_ => _))
    {
        if (last.HasValue && last.Value + 1 != next)
        {
            return last.Value + 1;
        }

        last = next;
    }

    return last.HasValue ? last.Value + 1 : Int32.MaxValue;
}

Answer 4

public static class IntExtensions
{
    public static int? SomeCoolLinqMethod(this IEnumerable<int> ints)
    {
        int counter = ints.Count() > 0 ? ints.First() : -1;

        while (counter < int.MaxValue)
        {
            if (!ints.Contains(++counter)) return counter;
        }

        return null;
    }
}

Usage:

var nextAvailable = myInts.SomeCoolLinqMethod();

Answer 5

Ok, here is the solution that I came up with that works for me.

var nextAvailableInteger = Enumerable.Range(myInts.Min(),myInts.Max()).FirstOrDefault( r=> !myInts.Contains(r));

If anyone has a more elegant solution I would be happy to accept that one. But for now, this is what I'm putting in my code and moving on.

Edit: this is what I implemented after Kevin's suggestion to add an extension method. And that was the real answer - that no single LINQ extension would do so it makes more sense to add my own. That is really what I was looking for.

public static int NextAvailableInteger(this IEnumerable<int> ints)
{
    return NextAvailableInteger(ints, 1); // by default we use one
}
public static int NextAvailableInteger(this IEnumerable<int> ints, int defaultValue)
{
    if (ints == null || ints.Count() == 0) return defaultValue;

    var ordered = ints.OrderBy(v => v);
    int counter = ints.Min();
    int max = ints.Max();

    while (counter < max)
    {
        if (!ordered.Contains(++counter)) return counter;
    }
    return (++counter);
}

Answer 6

Not sure if this qualifies as a cool Linq method, but using the left outer join idea from This SO Answer

var thelist = new List<int> {1,2,3,4,5,100,101};

var nextAvailable = (from curr in thelist
                    join next in thelist
                        on curr + 1 equals next into g
                    from newlist in g.DefaultIfEmpty()
                    where !g.Any ()
                    orderby curr
                    select curr + 1).First();

This puts the processing on the sql server side if you're using Linq to Sql, and allows you to not have to pull the ID lists from the server to memory.

Answer 7

var nextAvailable = myInts.Prepend(0).TakeWhile((x,i) => x == i).Last() + 1;

It is 7 years later, but there are better ways of doing this than the selected answer or the answer with the most votes.

The list is already in order, and based on the example 0 doesn't count. We can just prepend 0 and check if each item matches it's index. TakeWhile will stop evaluating once it hits a number that doesn't match, or at the end of the list.
The answer is the last item that matches, plus 1.
TakeWhile is more efficient than enumerating all the possible numbers then excluding the existing numbers using Except, because we TakeWhile will only go through the list until it finds the first available number, and the resulting Enumerable collection is at most n.
The answer using Except generates an entire enumerable of answers that are not needed just to grab the first one. Linq can do some optimization with First(), but it still much slower and more memory intensive than TakeWhile.