CODEWITHSUNDEEP
c#arrayslinq
Plus
Plus

Reputation: 37

Consecutive elements with consecutive sum greater than 0 using Linq

Alright, so this is only a small part of an interesting problem I solved a few days back. Imagine we have an array of N elements. The array consists only of 1s and -1s. It looks something like this:

int[] arr = new int[] { -1, 1, -1, 1, 1, -1 };

Our task is to find the maximum number of consecutive elements (left to right) that keep an (imaginary) counter >= 0, then cut the array so that only these elements are left.

In our case, we start with a counter of 0:

Counter = 0

First element: -1 -> Counter = -1 (Which is below 0, so we reset the counter)

Second: 1 -> Counter = 1

Third: -1 -> Counter = 0

Fourth: 1 -> Counter = 1

etc..

In the example stated above, the answer is:

Solve(new int[] { -1, 1, -1, 1, 1, -1 }); // => new int[] { 1, -1, 1, 1, -1 };

Now, my way of doing this was something along the lines of:

public static List<int> Solve(int[] input)
{
   List<List<int>> compare = new List<List<int>>();
   List<int> temp = new List<int>();
   for(int i = 0, c = 0; i < input.Length; i++)
   {
       if(input[i] == 1)
       {
           c++;
           temp.Add(input[i]);
       }
       else if(input[i] == -1)
       {
           c--;
           if (c >= 0)
               temp.Add(input[i]);
           else
           {
              c = 0;
              compare.Add(temp);
              temp = new List<int>();
           }
       }
   }

   compare.Add(temp);
   return compare.OrderByDescending(x => x.Count).First();
}

Some more test cases:

Solve(new int[] { -1, 1, -1, 1, 1, -1 }); // => new int[] { 1, -1, 1, 1, -1 };

Solve(new int[] { 1, 1, -1, -1, 1, 1 }); // => new int[] { 1, 1, -1, -1, 1, 1 };

Solve(new int[] { 1, -1, 1, -1, 1, -1, -1, 1, 1, 1 }); // => new int[] { 1, -1, 1, -1, 1, -1 };

Solve(new int[] { 1, 1, 1, -1, -1, 1, -1, 1, -1, 1, -1, -1, -1 } 
// => new int[] { 1, 1, 1, -1, -1, 1, -1, 1, -1, 1, -1, -1 };

Solve(new int[] { -1, -1, -1 }); // => new int[] { };

But my question for all of you Linq masterminds is: Is there any way to do this in 1 line of code, using our beloved Linq?

That would be greatly appreciated :D

Upvotes: 1

Views: 703

Answers (4)

user2051770
user2051770

Reputation: 764

If you HAVE to use Linq, and you can sort of cheat and use MoreLinq, then this ugly mess would work (it gives back multiple collections since you could in theory have multiple runs of the same max size)

Enumerable.Range(0, input.Count())
    .Select(i =>
        input.Skip(i)
             .Scan((Current: 0, Total: 0), (x, y) => (y, x.Total + y))
             .Skip(1)
             .TakeWhile(x => x.Total >= 0))
    .MaxBy(x => x.Count())
    .Select(x => x.Select(y => y.Current));

Upvotes: 1

Dave Holden
Dave Holden

Reputation: 167

I encountered this problem recently on a skills test that I had to do when applying for my job. You need very little code to solve it and no LINQ is required.

int currentLevel = 0;
List<int> lst = new List<int>();
for(int x = 0; x < input.length; x++) {
  currentLevel += input[x];
  if (currentLevel >= 0) {
    lst.Add(input[x]);
  }
}
return lst.ToArray();

Upvotes: 1

Kit
Kit

Reputation: 21739

I agree with the other answers suggesting LINQ is probably not the best approach. Here's my take. This version only replaces a shorter sequence with a longer sequence to avoid some memory overhead and the OrderByDescending step can then be skipped as well.

public static List<int> Solve(int[] input)
{
    var temp = new List<int>();
    var longestSequence = new List<int>();

    for (int i = 0, c = 0; i < input.Length; i++)
    {
        c += input[i];

        if (c >= 0)
            temp.Add(input[i]);
        else
        {
            c = 0;
            if (temp.Count > longestSequence.Count)
                longestSequence = temp;
            temp = new List<int>();
        }
    }

    return longestSequence;
}

If you get really concerned about memory allocations such as copying to a temp list and list resizing operations under the covers, then you can just keep track of the start and end of the sequence instead, then loop over that returning the subsequence.

Upvotes: 1

Guru Stron
Guru Stron

Reputation: 143233

In this particular case due to relatively complex condition logic I would say that using iterational approaches is better alternative but some similar tasks can be solved by using Aggregate functions which applies an accumulator function over a sequence and allows you to pass state between the steps. For your case it can look something like this (using some C# 9 features):

var result = arr
    .Select((i, index) => (i, index))
    .Aggregate(
        (Sum: 0, Ranges: new List<List<int>> {new()}), // state holder 
        (agg, curr) =>
        {
            var sum = curr.i + agg.Sum;
            if (sum >= 0) agg.Ranges.Last().Add(curr.i);
            if (sum < 0)
            {
                sum = 0;
                agg.Ranges.Add(new());
            }

            return (sum, agg.Ranges);
        })
    .Ranges
    .Aggregate((agg, curr) => curr.Count > agg.Count ? curr : agg); // MaxBy via Aggregate

Upvotes: 1

Related Questions