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

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();

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();

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 :)

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;
}

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();

Answer 6

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.

Answer 7

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);