Can LINQ be used to find gaps in a sorted list?

Question

Is it possible for me to use LINQ in a way that allows me to determine that "9" is the first missing value in the sorted list without using a for-loop and comparing each value to the one adjacent to it?

var listStringVals = new [] { "7", "13", "8", "12", "10", "11", "14" };
// sort list to "7","8","10","11","12","13","14"
var sortedList = listStringVals.OrderBy(c => int.Parse(c)).ToList();
// need some magic here to get the first gap in the sorted list

Tumefaction

Just curious; why are they string and not like int or something? – Olwen

A loop will end up being the easiest and clearest way to write this in C#. – Mattox

@Olwen - They are strings because they represent part of an ID string that was stored in a database. I'm just playing with LINQ, trying to get a better feel for when it can simplify certain tasks. – Tumefaction

Answer 1

Let

var strings = new string[] { "7", "13", "8", "12", "10", "11", "14" };

Then

var list = Array.ConvertAll(strings, s => Int32.Parse(s)).OrderBy(i => i);
// or
var list = strings.Select(s => int.Parse(s)).OrderBy(i => i);
// or
var list = strings.OrderBy(s => int.Parse(s));

(note this question)

and then

var result = Enumerable.Range(list.Min(), list.Count).Except(list).First(); // 9
// or
int min = list.Min(), max = list.Max();
var result = Enumerable.Range(min, max - min + 1).Except(list).First();

Seiden

actually, instead of list.Count should it compare to the last item, which is the highest value? If there are only 5 items but the last item is 1000 this will not return all gaps, only gaps up to the number 5 – Nonscheduled

@hunter; you are correct, which is what I covered in my answer, actually =) – Olwen

@Nonscheduled - my initial question was just to find the first gap, but it could be useful to find all gaps in other situations. – Tumefaction

@Nate... this doesn't work like you think. If your list was { 7, 8, 10, 1000 } result will be 11, not 11 to 999 – Nonscheduled

@Tumefaction -- just change the list.Count to list.Max() - list.Min() + 1. – Olwen

Thanks for the claification, just for the record, I understand the differences. This method will only return the first singular value, where some of the other answers return entire sets of missing numbers. Also worth noting that this method will generate an exception if the list does not contain any gaps. – Tumefaction

@hunter, @Nate: I edited my answer. Thanks for acceptance and criticism! :) – Seiden

Answer 2

Here's a way to get you started (I used int values here):

List<int> listStringVals = (new int[] { 7, 13, 8, 12, 10, 11, 14 }).ToList();
List<int> SortedList = listStringVals.OrderBy(c => c).ToList();
List<int> Gaps = Enumerable.Range(SortedList.First(), 
                                  SortedList.Last() - SortedList.First() + 1)
                           .Except(SortedList).ToList();

Olwen

Excellent, thank you for illustrating a nice way to get all the gaps. This post has generated some awesome answers, it is a shame I can only tag one as the answer. Thanks everybody! – Tumefaction

+1 for bothering to write the correct Range calculation at the start! – Vevine

Answer 3

var listStringVals = new string[] {"7", "13", "8", "12", "10", "11", "14"};
var sortedInts = listStringVals.Select(c => int.Parse(c)).OrderBy(x => x);
var noGaps = Enumerable.Range(sortedInts.First(), 
                              sortedInts.Last() - sortedInts.First() + 1);
var missing = noGaps.Except(sortedInts).Select(x => x.ToString()).First();

Edit: fixed range generation thanks to BeemerGuy's answer. Still leaving mine, as it doesn't ignore the ugliness of a list of string representations of ints :)

Vevine

Answer 4

(abatishchev beat me to the punch, but his answer is better anyway. However, since alternate solutions to the same problem can be fun, I am still posting this.)

Hackity hack hack. But working, if you really want to do this. Performance will be awful, because this technique will not stop when it finds the answer -- it will always loop over every number! But it will work:

public static int FindFirstMissing(IEnumerable<int> sequence)
{
    bool found = false;

    int agg = sequence.Aggregate((aggregate, next) => {
        if (found)
            return aggregate;

        if (next - aggregate != 1) {
            found = true;
            return aggregate + 1;
        }

        return next;
    });

    if (!found)
        throw new ArgumentException("sequence", "Contains no missing numbers.");

    return agg;
}

Zenda

Really cool! Aggregate() is the most power tool in the set, I think. But a bit complex in the same time. – Seiden

And not efficient for cases like this. ;) – Zenda

+1 for a new approach, I haven't reviewed responses to this question in a long time but this one is interesting. Thanks to everyone that took the time to post, I appreciate the time and perspective. – Tumefaction

Answer 5

string firstGap = sortedList
    .Zip(sortedList.Skip(1), (f, s) => Tuple.Create(f, s))
    .First(tup => (int.Parse(tup.Item1) + 1) != int.Parse(tup.Item2)).Item1;

Should give you the first item before the first gap, so the first missing element is:

string gap = (int.Parse(firstGap) + 1).ToString();

Aylesbury

Very creative way to solve the problem, I've really enjoyed reading all the answers! – Tumefaction

@Vevine - It creates a sequence of pairs between an item in the list and the following item e.g. ("7","8"), ("8","10)...("11","14"). The third line looks for the first tuple where the first element is not one less than the second. – Aylesbury

thanks for the explanation (sorry for deleting my comment) - I've been playing with it for the last 20 minutes and had actually just groked what it did when I noticed your comment. – Vevine

I like this solution best, as it finds the actual gaps instead of the numbers that are not in the list. var gaps = a.Zip(a.Skip(1), (l, r) => new[] { l + 1, r - 1 }).Where(p => p[0] <= p[1]) – Madore

Answer 6

It's a little late but I think it's a cool way of doing this:

List<int> listStringVals = (new int[] { 7, 13, 8, 12, 10, 11, 14 }).ToList();
            listStringVals.Sort();
            return listStringVals.Skip(1).Select((x, i) => x - listStringVals[i] == 1).Any(x => !x);

Voight

I love to see different approaches to solving the same problem. Thanks for posting, even if it is a bit late. Taking the time to grok all the different answers has already paid off in spades. Thanks again to everyone that took their time to post on this thread. – Tumefaction

Answer 7

Why not just use All since all of the members in the collection need to conform to the criteria...

Example

someVar.All(v => someVar.Contains(v + 1) || v == someVar.Last())

Then you don't have to order and its nicer.

You could sort after this step or even during if you needed to but I personally would just use the sorted collection and have it do that work for me.

You would grab the values if you needed to after doing the check then return the result of the check or hide it if you wanted to for some reason via a multi-line modification above along with a list to store the values in.

e.g.

someVar.All((v) => { 
    bool result = someVar.Contains(v + 1) || v == someVar.Last();
    if(!result) someList.Add(v);
    return true;
});

Checking the count of the list (which could be ordered) for a non zero value to indicate if it satisfied or not.

Synchroscope