Split List into sublists based on border values

Question

I would like to split up an existing sorted list into multiple sublists, based on the entries of another list.

Let's say I have an array like this:

List<int> myList = [1,3,7,23,56,58,164,185];

and another list, which defines at which places myList should be split:

List<int> borders = [4,59,170];

What's the shortest way to get a nested list where myList is split at the values defined in borders, i.e. like this:

[[1,3],[7,23,56,58],[164],[185]]

I have already solved it by manually looping through the lists, but I can imagine it's easier and shorter using Linq.

EDIT: There is one simplification: numbers can't be the same as the borders, so it's impossible that a number is contained in myList and borders at the same time.

Answer 1

Since you want to group the numbers into different groups, you will want to use GroupBy. The difficulty is only what you use as the key. For this, you can use the largest border value that is smaller than the number. This assumes that borders is sorted though:

List<int> myList = new List<int> { 1, 3, 7, 23, 56, 58, 164, 185 };
List<int> borders = new List<int> { 4, 59, 170 };

var groups = myList.GroupBy(i => borders.LastOrDefault(x => x < i));

foreach (var group in groups)
{
    Console.WriteLine("{0}: {1}", group.Key, string.Join(", ", group));
}

This yields the following output:

0: 1, 3
4: 7, 23, 56, 58
59: 164
170: 185

Note that this is not exactly the most efficient solution as it will search for an appropriate border key for every element in myList. If your list is sorted like your example, then it’s more efficient to loop through both at the same time and just match the numbers of myList to the current or next border element. So this solution is O(n * m) while a solution O(n) is possible. On the plus side, this allows myList to be completely unsorted.

---

For those interested in a O(n) solution, here’s one possible take on it which is just a very general way on grouping sequences:

List<List<int>> groups = new List<List<int>>();
List<int> group = null;
int k = -1;
foreach (int num in myList)
{
    if (k < 0 || num > borders[k])
    {
        group = new List<int>();
        groups.Add(group);
        k++;
    }
    group.Add(num);
}