CODEWITHSUNDEEP
c#algorithmlinqtime-complexity
Micro Optimizer
Micro Optimizer

Reputation: 227

Most efficient way to find a "space" in an ordered list using LINQ

What I'm trying to do is something like if iterating through something like

IEnumerable<int> ids = items.Select(item => item.Id);

which is 0 1 5 7

then I want to select 2 because that's the smallest number i in the range [0, 7+1] such that i-1 is in the list while i isn't. If 0 isn't in the list, then 0 gets chosen, however.

What is the most compact, efficient, readable, fancy, and LINQiest way to do this?

Let me know if I need to give a more thorough explanation.

Upvotes: 2

Views: 162

Answers (4)

vibhuti
vibhuti

Reputation: 11

For finding index of first gap, please try this if it fits in your requirement.

 int[] items = new int[] { 0,1, 3, 4, 6 }; 
 var firstGap = items.Select((index, value) => new { value, index })
                     .FirstOrDefault(c => c.value == 0 ? items[c.value] != 0 : items[c.value] != items[c.value - 1] + 1).value;

Upvotes: 0

tmaj
tmaj

Reputation: 35075

Here's my take:

    private static int GetGap(int[] items)
    {
        // return items.TakeWhile((v, i) => v == i).Select(i => i + 1).LastOrDefault();
        if (!items.Any()) return 0;
        if (items.First() != 0) return 0;
        int counter = 0;
        return items.ToList().LastOrDefault(x => x == counter++) + 1;
    }

Tests:

   public static IEnumerable TestCases
    {
        get
        {
            yield return new TestCaseData(new int[] { 0, 1, 5, 7 }, 2).SetName("1");
            yield return new TestCaseData(new int[] { 0, 1, 2, 3, 4 },5).SetName("2");
            yield return new TestCaseData(new int[] { 1, 2, 3, 4 },0).SetName("3");
            yield return new TestCaseData(new int[] { -2, -1, 1, 2, 3, 4 }, 0).SetName("4");
            yield return new TestCaseData(new int[] { -2, -1, 0, 1, 2, 3, 4 },0).SetName("5");
            yield return new TestCaseData(new int[] { 0 },1).SetName("6");
            yield return new TestCaseData(new int[] { },0).SetName("7");

        }
    }

    [TestCaseSource("TestCases")]
    public void Test(int[] items, int expected ) {
        Assert.AreEqual(expected, GetGap(items));
    }

Upvotes: 1

Scott Chamberlain
Scott Chamberlain

Reputation: 127593

It would not be hard to write your extension method to do this. 

    //examples
    class Program
    {
        static void Main(string[] args)
        {
            //Your original example
            var items = new List<int> { 0, 1, 5, 7 };
            var gap = items.FindFirstGap();
            Console.WriteLine(gap); //shows 2

            //No gaps
            items = new List<int> { 0, 1, 2, 3 };
            gap = items.FindFirstGap();
            Console.WriteLine(gap); //shows 4

            //no 0
            items = new List<int> { 1, 2, 3, 4 };
            gap = items.FindFirstGap();
            Console.WriteLine(gap); //shows 0

            Console.ReadLine();
        }
    }

The below solution is O(N) and supports any struct datatype you can provide a function to calculate "+ 1" and "Equals" for. I made a overloads that does all of the base integer types logic for you so you don't need to specify it at the caller.

using System;
using System.Collections.Generic;

namespace ConsoleApplication1
{
    public static class ExtensionMethods
    {
        public static T FindFirstGap<T>(this IEnumerable<T> @this, Func<T, T> getNext, IEqualityComparer<T> comparer) where T : struct
        {
            using (var enumerator = @this.GetEnumerator())
            {
                T nextItem = default(T);
                while (enumerator.MoveNext())
                {
                    var currentItem = enumerator.Current;
                    if (!comparer.Equals(currentItem, nextItem))
                        return nextItem;
                    nextItem = getNext(currentItem);
                }
                return nextItem;
            }
        }

        public static T FindFirstGap<T>(this IEnumerable<T> @this, Func<T, T> getNext) where T : struct
        {
            return FindFirstGap(@this, getNext, EqualityComparer<T>.Default);
        }

        public static int FindFirstGap(this IEnumerable<int> @this)
        {
            return FindFirstGap(@this, i => i + 1, EqualityComparer<int>.Default);
        }

        public static long FindFirstGap(this IEnumerable<long> @this)
        {
            return FindFirstGap(@this, i => i + 1, EqualityComparer<long>.Default);
        }

        public static short FindFirstGap(this IEnumerable<short> @this)
        {
            return FindFirstGap(@this, i => (short)(i + 1), EqualityComparer<short>.Default);
        }

        public static byte FindFirstGap(this IEnumerable<byte> @this)
        {
            return FindFirstGap(@this, i => (byte)(i + 1), EqualityComparer<byte>.Default);
        }
    }
}

Upvotes: 2

zerkms
zerkms

Reputation: 255005

For the non-empty collections this might be the shortest possible implementation, it is O(N) though (it also assumes Id field you have is numeric, does not change anything though):

var missingIndex = list.TakeWhile((v, i) => v == i).Last() + 1;

How it works: it iterates over a list until the value matches its index. Then after some value does not match its index - is a gap.

UPD

with the help of @Rob it was fixed to handle lists that start with non-zeroes:

var missingIndex = list.TakeWhile((v, i) => v == i).Select(i => i + 1).LastOrDefault();

For the efficient solution you need to employ a binary search which would look better in the imperative style (see non-linq'y).

Upvotes: 7

Related Questions