Finding the most popular element with C# given O(1) space complexity requirement I have tried to solve the following problem in C# with LINQ:


  Given an integer array, find the most frequent number and it's count in the array. If multiple numbers have the same highest frequency return the smallest number.


One requirement here is also to make the code execute in O(1) space complexity.

public struct MostPoularItem
{
    public MostPoularItem(int item, int count)
    {
        Item = item;
        Count = count;
    }

    public int Item { get; }
    public int Count { get; }
}

public static class Utils
{
    public static MostPoularItem FindMostPopularElement(int[] integers)
    {
        if(integers == null) 
        {
            throw new ArgumentNullException(nameof(integers));
        }

        return integers.GroupBy(x =&gt; x)
            .OrderBy(x =&gt; x.Key)
            .OrderByDescending(x =&gt; x.Count())
            .Select(x =&gt; new MostPoularItem(x.Key, x.Count()))
            .FirstOrDefault();
    }
}


Would be nice to have someone else's eye on this, especially around trying to see if there is any room of improving its time and space complexity. Feel free to offer alternative solutions which don't also use LINQ as well.
You don't have \$O(1)\$ space complexity at the moment, OrderBy and OrderByDescending (used wrong as pointed out in the other answer(s)) will have a non-constant space complexity.

Since runtime is not the problem here, we can make this a space complexity of \$O(1)\$ pretty easily:

Tuple&lt;int, int&gt; GetItemWithMaxCount(int[] items)
{
    var maxCount = 0;
    var maxItem = 0;

    for (int i = 0; i &lt; items.Length; i++)
    {
        var currentCount = 1;
        var currentItem = items[i];

        foreach (var item in items.Skip(i + 1))
        {
            if (item == currentItem)
            {
                currentCount++;
            }
        }

        if (currentCount &gt; maxCount)
        {
            maxCount = currentCount;
            maxItem = currentItem;
        }
        else if (currentCount == maxCount)
        {
            if (currentItem &lt; maxItem)
            {
                maxItem = currentItem;
            }
        }
    }

    return new Tuple&lt;int, int&gt;(maxItem, maxCount);
}


Return an actual class if you like.

The downside of this? Time complexity is \$O(n^2)\$ (I think), but it's guaranteed to use constant space. We also cannot build a lookup of previous iterations, as that would use more than constant space.

Essentially, we just loop through all the items n times, then loop from that item on. This is a trick to help us prevent iterating the same item multiple times. We know that each index can only have a specific value in it so we can skip the that value (and all previous ones) in the inner loop.

There's no complex LINQ here, no additional arrays, no sorting. Just go through them all and add them up then compare to the current max. The .Skip(i + 1) method is part of LINQ, but you can get around that pretty easily by changing that iteration up (swap the foreach out):

for (int j = i + 1; j &lt; items.Length; j++)
{
    if (items[j] == currentItem)
    {
        currentCount++;
    }
}


This can be ordered, unordered, whatever. It meets all your criteria: return item with most counts and count or lowest value item with most counts and count if a tie.

This solution is similar (has the same general effect) to the solution presented in this answer by Peter Taylor, but the key advantage here is that we can optimize it for our requirements. We've already made one optimization: skilling the first i elements. Just as well, that answer will not use constant space because of Select, which appears to use a significant amount of space.

As an example, you can increase speed (slightly) by skipping duplicates as we can with our constant space requirement:

for (int i = 0; i &lt; items.Length; i++)
{
    var currentCount = 1;
    var currentItem = items[i];

    if (currentItem == maxItem)
    {
        continue;
    }

    foreach (var item in items.Skip(i + 1))


Basically, that if will mean that if we are iterating a value again (mind you, it can change, so we can still check the same value twice, but if it's the current max we'll skip it to maintain our space complexity) we can skip it for the moment.



If you read about LINQ-to-objects (which is what we're using) it uses a Stable Quicksort to do it's sorting.

One thing we know about quicksort is that worst-case space complexity is \$O(n)\$ for a naive implementation, and \$O(log(n))\$ for an optimized implementation.

This means that any solution presented that uses LINQ to order the elements is going to use \$O(log(n))\$ space complexity.

And of course, I have to prove that this uses \$O(1)\$ space (or, at least, less space than the OP) so I ran BenchmarkDotNet against my code and OP code:

            Method |            Mean |      StdDev |   Gen 0 | Allocated |
------------------ |---------------- |------------ |-------- |---------- |
      OriginalCode |   1,718.1155 us |   7.6080 us |       - | 327.31 kB |
      EBrownAnswer |  28,547.8824 us |  48.4272 us |       - |     512 B |


Mine took 130 times as long (expected) but ran in 0.15% of the space. So, how do the other answers stack up?

Well, once we put all the answers together (the one by Peter Taylor doesn't return the correct object, but let's just try that one out as well anyway) we get the following:

            Method |            Mean |      StdDev |   Gen 0 | Allocated |
------------------ |---------------- |------------ |-------- |---------- |
      OriginalCode |   1,718.1155 us |   7.6080 us |       - | 327.31 kB |
      EBrownAnswer |  28,547.8824 us |  48.4272 us |       - |     512 B |
  RubberDuckAnswer |   1,183.3647 us |   3.5244 us | 20.3125 | 302.64 kB |
 PeterTaylorAnswer | 255,862.3770 us | 201.6448 us |       - | 760.33 kB |
   HeslacherAnswer |      62.5081 us |   0.3105 us |       - |   8.23 kB |
   PaparazziAnswer |     882.7228 us |   2.9597 us |       - | 157.98 kB |


So there we have it. Looks like the only version that actually had \$O(1)\$ space complexity was the version I posted here. If you can relax that requirement slightly then the version Heslacher posted is the most superior version to use.

If you want a truly optimal solution based off of both metrics of each method (we'll define best as the lowest of time * memoryInBytes), we have the following:

           Method |          Weighted Result |
----------------- |------------------------- |
     OriginalCode |     575,852,937.5283 usB |
     EBrownAnswer |      14,616,515.7888 usB |
 RubberDuckAnswer |     366,728,696.6354 usB |
PeterTaylorAnswer | 199,208,797,290.9158 usB |
  HeslacherAnswer |         526,728.4275 usB |
   PaparazziAnswer|     142,799,409.0947 usB |


The answer posted by Heslacher comes in first, again.

Do note, however, that method is not without it's flaws. As the range between integers grows bigger, the method uses more space. If we're using unbounded int ranges, Heslacher's answer will not work at all. (It will crash on negatives and on extremely large ranges.)

Do note: list generation is not measured for each of these methods and is defined as:

const int _integerCount = 10000;

private static int[] GetItems()
{
    var list = new int[_integerCount];
    var rand = new Random(0);

    for (int i = 0; i &lt; _integerCount; i++)
    {
        list[i] = rand.Next(0, 2048);
    }

    return list;
}


So, if we adjust our integer range to fall within 0 and short.MaxValue (32767), we get the following results:

          Method |           Mean |     StdDev |   Gen 0 |   Gen 1 |   Gen 2 | Allocated |     Result Weighted |
---------------- |--------------- |----------- |-------- |-------- |-------- |---------- |-------------------- |
    EBrownAnswer | 28,408.5030 us | 34.7946 us |       - |       - |       - |     512 B | 14,545,153.5360 usB |
 HeslacherAnswer |    119.7295 us |  0.4404 us | 36.8164 | 36.8164 | 36.8164 | 131.42 kB | 16,112,487.3114 usB |


As this shows, our fastest answer is not always the best. For large ranges of integers (or anything above ~500m, or any values below 0) that solution will fail, sadly. :(

And believe it or not, for small, highly-variable data-sets this algorithm is the fastest (number count = 100, vary from 0 to short.MaxValue):

            Method |       Mean |    StdDev | Scaled | Scaled-StdDev |   Gen 0 |   Gen 1 |   Gen 2 | Allocated |
------------------ |----------- |---------- |------- |-------------- |-------- |-------- |-------- |---------- |
      OriginalCode | 39.0327 us | 0.1790 us |   1.00 |          0.00 |  0.5615 |       - |       - |   9.91 kB |
      EBrownAnswer |  4.6140 us | 0.3984 us |   0.12 |          0.01 |       - |       - |       - |      16 B |
  RubberDuckAnswer | 25.2577 us | 0.0717 us |   0.65 |          0.00 |  0.3499 |       - |       - |   8.39 kB |
 PeterTaylorAnswer | 34.0133 us | 0.1991 us |   0.87 |          0.01 |  0.0651 |       - |       - |   7.76 kB |
   HeslacherAnswer | 30.2370 us | 0.0269 us |   0.77 |          0.00 | 40.3239 | 40.3239 | 40.3239 | 131.42 kB |
   PaparazziAnswer | 17.5162 us | 0.0507 us |   0.45 |          0.00 |  0.5412 |       - |       - |   6.09 kB |