Nate
Nate

Reputation: 901

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

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

Upvotes: 27

Views: 15215

Answers (7)

Jay
Jay

Reputation: 3355

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.

Upvotes: 1

jball
jball

Reputation: 25014

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

Upvotes: 5

Saeed Amiri
Saeed Amiri

Reputation: 22565

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

Upvotes: 1

abatishchev
abatishchev

Reputation: 100308

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

Upvotes: 64

Lee
Lee

Reputation: 144176

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

Upvotes: 3

cdhowie
cdhowie

Reputation: 169143

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

Upvotes: 3

BeemerGuy
BeemerGuy

Reputation: 8269

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

Upvotes: 17

Related Questions