Algorithm to find sequential ID gaps in List<long>

Question

I had to develop an algorithm that will find gap between sequential Ids within a List<long>.

For example as input we had the following List<long> = {1,2,3,6,7,8,11,12,15,16}. This means that algorithm should find the numbers 4,5,9,10,13,14 .

For this task I developed the following method, but not sure about effectiveness of this method in case of large data input, also about clean code readability.

        private const int AllowedGap = 1;

        public static List<long> FindMissingSequentialIDs(List<long> ids)
        {
            List<long> response = new List<long>();

            for (int i = 0; i < ids.Count() - 1; i++)
            {
                if (ids[i + 1] - ids[i] > AllowedGap)
                {
                    long currentGapCount = ids[i + 1] - ids[i] - 1;

                    long missedSeqId = 0;
                    while (currentGapCount != 0)
                    {
                        if (missedSeqId == 0)
                        {
                            missedSeqId = ids[i + 1] - 1;
                            response.Add(missedSeqId);

                            currentGapCount--;

                            if (currentGapCount == 0)
                            {
                                break;
                            }
                        }

                        else
                        {
                            missedSeqId = missedSeqId - 1;

                            response.Add(missedSeqId);

                            currentGapCount--;
                        }
                    }
                }
            }

            return response;
        }

Seems like this worked , but what would you improve here ?

Answer 1

If you're allowed to use LINQ, you can simplify. Essentially create a lazily-evaluated Range of numbers from the min to the max, then exclude those in your list, return that final lazily-evaluated list and iterate over it.

private static IEnumerable<long> GetGaps(IEnumerable<long> list)
{
    return Range(list.Min(), list.Max()).Except(list);
}

private static IEnumerable<long> Range(long start, long count)
{
    long max = start + count - 1L;
    
    if (count < 0 || max > long.MaxValue)
    {
        throw new ArgumentOutOfRangeException(nameof(count));
    }
    
    return RangeIterator(start, count);
}

private static IEnumerable<long> RangeIterator(long start, long count)
{
    for (long i = 0L; i < count; i++)
    {
        yield return start + i;
    }
}

Answer 2

using Count() extension would count the elements of the collection on each iteration, which would impact the performance, and since you're using List<long> you can use Count property instead. ids.Count.

Current code can be simplified to something like this :

// assuming all elements are positive integers
public static IEnumerable<long> FindMissingSequentialIDs(List<long> ids)
{
    if(ids == null) throw new ArgumentNullException(nameof(ids));

    if (ids.Count == 0) yield break;
    
    ids.Sort(); // sort the elements first

    for (var i = 0; i < ids.Count - 1; i++)
    {
        var current = ids[i];

        var next = ids[i + 1];

        var gap = next - current;

        if (gap == AllowedGap) continue;

        for (var x = current + 1; x < next; x++)
            yield return x;
    }
}

This code will only read and return the missing, which means less memory allocation. You can then hook it up with another iterator or just use ToList to store the results into a new list.

Example :

var missing = FindMissingSequentialIDs(ids).ToList();

Answer 3

Your code seems to be very low level and optimzed for performance (excepting the call of Count() that was already mentioned by iSR5). However, most cases do not require that micro performance optimization so if there is no performance problem, I would go with a readable and maintainable version of the algorith.

That is usualy the usage of LINQ methods:

private static IEnumerable<int> FindGaps(List<int> list)
{
    var min = list[0];
    var max = list[list.Count - 1];
    var set = new HashSet<int>(list);
    
    return Enumerable.Range(min, max-min).Where(i => !set.Contains(i));
}

The parameter 'AllowedGap' should be passed to the method instead of defined as static field. That "extra rule" makes the algorithm a bit more complex, but I would still prefer working with lists instead of counting indices.

private static IEnumerable<int> FindGaps(List<int> list, int allowedCapCount = 1)
{
    if (list.Count == 0)
    {
        return new int[0];
    }
    
    var min = list[0];
    var max = list[list.Count - 1];
    var existing = new HashSet<int>(list);
    var stack = new List<int>();
    var gaps = new List<int>();

    foreach (var item in Enumerable.Range(min, max - min))
    {
        if (existing.Contains(item))
        {
            if (stack.Count >= allowedCapCount)
            {
                gaps.AddRange(stack);
            }
            stack.Clear();
        }
        else
        {
            stack.Add(item);
        }
    }
    
    gaps.AddRange(stack);
    
    return gaps;
}