# 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 => x)
.OrderBy(x => x.Key)
.OrderByDescending(x => x.Count())
.Select(x => 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.

• LINQ is compact but it is not efficient. Why are you limiting to LINQ? – paparazzo Dec 21 '16 at 14:37
• @Paparazzi I just wanted to see if that would be possible with LINQ. I will change to the question to reflect that it doesn't have to be LINQ :) – tugberk Dec 21 '16 at 14:45
• Also, for what it's worth, this is not O(1) space complexity. – 410_Gone Dec 21 '16 at 19:13

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<int, int> GetItemWithMaxCount(int[] items)
{
var maxCount = 0;
var maxItem = 0;

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

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

if (currentCount > maxCount)
{
maxCount = currentCount;
maxItem = currentItem;
}
else if (currentCount == maxCount)
{
if (currentItem < maxItem)
{
maxItem = currentItem;
}
}
}

return new Tuple<int, int>(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 < 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 < 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 |


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 < _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 |

• And note that GroupBy cannot possibly use any less than O(n) space, so the OP's implementation will never be any better than that. – Servy Dec 21 '16 at 19:46
• How do you get 8.23 kB for Heslacher? An Int32 is 4 bytes. – paparazzo Dec 21 '16 at 19:52
• @Paparazzi Because the range of integers was 0 to 2048, 2048 * 4 ~8192 (8.23kB). If the range is from int.MinValue to int.MaxValue, Heslacher's solution will throw an exception. – 410_Gone Dec 21 '16 at 19:52
• If you optimise quicksort for space rather than for constant factor in the time then you can get it to run in constant space and O(n lg n) time. I'm not sure that anyone has ever written an implementation that does that, but it's doable. Also note that (as pointed out by Servy in a different comment thread) "Allocated" doesn't tell you the space complexity. for (int i = 0; i < N; i++) var b = new int[1];has O(1) space complexity, but unless the compiler optimises heavily it allocates O(N) space. – Peter Taylor Dec 22 '16 at 10:48
• @Paparazzi BenchmarkDotNet - I dropped all the code for everyone's answer in a class, added a NameAnswer() method that called PersonCodeMethod() with the [Benchmark] attribute and fed the list (a private readonly field populated with GetItems() to it. BenchmarkDotNet is taking the average of the execution times on my machine for the report. Every algorithm was fed the exact same list. – 410_Gone Dec 22 '16 at 18:48
    return integers.GroupBy(x => x)
.OrderBy(x => x.Key)
.OrderByDescending(x => x.Count())
.Select(x => new MostPoularItem(x.Key, x.Count()))
.FirstOrDefault();


Calling OrderByDescending after OrderBy will destroy the previous sorting.

If you want to apply another sorting I think you mean to do it for a group and not the entire collection. In this case you should use ThenByDescending.

return integers
.GroupBy(x => x)
.OrderBy(x => x.Key)
.ThenByDescending(x => x.Count())
.Select(x => new MostPoularItem(x.Key, x.Count()))
.FirstOrDefault();


Disclaimer: My review is not about the space complexity but pointing out the OrderBy-bug.

See the amazing review by @EBrown's for detailed information and benchmarks.

Your solution appears to be correct, although I can't speak to the space complexity of it. Linq makes complex things look easy. There's a lot going on "behind the scenes" here.

Anyway, let's look at the heart of your code here.

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


My biggest (only?) complaint about this code is that you've made it harder to understand than it needs to be by reusing the x identifier for a number of different things. Here's an alternative that I think makes it a bit easier to read.

    return integers.GroupBy(n => n)
.OrderBy(group => group.Key)
.OrderByDescending(group => group.Count())
.Select(group => new MostPoularItem(group.Key, group.Count()))
.FirstOrDefault();


This makes it more clear that after the GroupBy call, we're no longer working with an IEnumerable<int>, but with an IEnumerable<IGrouping<int,int>>. I've found that people are a bit too quick to overly shorten variable names in lambda expressions. Having a short scope doesn't excuse us from naming variables well.

• "Having a short scope doesn't excuse us from naming variables well." I think the salient point was that in a single expression it's being used for different things (though even then, I still think it's pretty clear by context). Certainly if you start introducing nested y and z things are quickly getting out of control. But if you're interacting with one type only, I think a single letter variable is as valid as using i in a for loop when there's no nesting. (though obviously subjective) – Kirk Woll Dec 21 '16 at 1:51
• It can be valid @KirkWoll, yes. You're also right that reusing the identifier was the main problem, but I've noticed this trend toward single letter variable names as if the fact that it's a lambda expression prevents us from using more descriptive identifiers... It's just an observation I've made. – RubberDuck Dec 21 '16 at 2:00
• I concur with your observation, and when my code is reviewed I've had to fix some of that up in my own code! ;) – Kirk Woll Dec 21 '16 at 2:02
• @KirkWoll cough I might get called out on it a fair bit at work myself... – RubberDuck Dec 21 '16 at 2:06
• Calling OrderByDescending after OrderBy will distroy the previous sorting, I think you meant to use ThenByDescending to sort within key scope by Count also enumerating the group twice with the Count() can hurt performance. If you need to use it twice then projecting it into a new type with Select might be faster. – t3chb0t Dec 21 '16 at 7:09

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

That's going to preclude an elegant solution (with or without Linq). In particular, GroupBy uses O(n) space, so that's out. (So's OrderBy). Technically you could say

integers.Select(i => new MostPopularItem(i, integers.Where(j => i == j).Count()))
.Max(mpi => mpi.Count)


but that's hideous.

The nicest solution I can see with that space complexity is to quick-sort in place (assuming that's permitted) and then do a linear scan to count each distinct value. But that's not Linq, and I wouldn't be surprised to learn that modifying the input is banned. (Although in that case why is it an int[] instead of an IReadOnlyList<int>?)

• This code returns the largest count of the items, but not the MostPopularItem for that largest count. – 410_Gone Dec 21 '16 at 18:49
• And I just learned that this doesn't use O(1) space either, looks like Select creates a new list instance before Max is called. – 410_Gone Dec 21 '16 at 19:04
• @EBrown Select is O(1) space. It allocates an iterator object, but it's just one object; it doesn't scale in memory with the size of the sequence, so it's O(1). – Servy Dec 21 '16 at 19:47
• @EBrown That would make it a problem with your testing approach then. For starters, total memory used tells you nothing about the big O of the space complexity. To see that you need to graph it as the size of the list increases. But anyway, like I said, nothing in this code is going to hold any non-constant amount of memory, so clearly something is wrong in how you're testing it. LIke I said, the very small data set is likely at least one problem. – Servy Dec 21 '16 at 19:59
• @EBrown So I see what you did wrong. You're looking at the total amount of memory allocated. This approach allocates lots of memory, but it's all extremely short lived. There is never more than a constant amount of memory that's rooted at any one time, but lots of memory is created and immediately aging, which you counted in your test. – Servy Dec 21 '16 at 20:03

Validation

if(integers == null)
{
throw new ArgumentNullException(nameof(integers));
}


well, this is a start but do you think that an array containing no elements should be seen as valid ? IMO no. So another validation needs to take place like so

if (integers.Length == 0)
{
throw new ArgumentOutOfRangeException("Passed in array doesn't contain any items");

}


To speed this up for the edge case that the array only contains one item I would add

if (integers.Length == 1)
{
return new MostPoularItem(integers[0], 1);
}


That being said, I would like to show a way using arrays where the complexity surely won't fit your needs but it is pretty fast.

I will use a second array which is as big as the biggest number in integers to count the number of occurances like so

public static MostPoularItem FindMostPopularElement(int[] integers)
{
if (integers == null)
{
throw new ArgumentNullException("integers");
}
if (integers.Length == 0)
{
throw new ArgumentOutOfRangeException("Passed in array doesn't contain any items");

}
if (integers.Length == 1)
{
return new MostPoularItem(integers[0], 1);
}

int[] counts = new int[integers.Max() + 1];

int maxCount = -1;
int maxItem = int.MaxValue;

for (int i = 0; i < integers.Length; i++)
{
int value = integers[i];
counts[value] += 1;

if (counts[value] > maxCount)
{
maxCount = counts[value];
maxItem = value;
}
else if (counts[value] == maxCount && maxItem > value)
{
maxItem = value;
}
}

return new MostPoularItem(maxItem, maxCount);

}


Using poor man benchmarking (using stopwatch including warm up) and filled the integers like so

Random rand = new Random();
int[] values = new int[10000001];
for (int i = 0; i < 10000000; i++)
{
values[i] = rand.Next(1000000);
}


the timings are for 10 runs

@t3chb0t : 77598 ms
@Paparazzi: 19254 ms
mine: 1198 ms

• Thanks! Did you mean to have int[] counts = new int[integers.Length + 1]; instead of int[] counts = new int[integers.Max() + 1];? – tugberk Dec 21 '16 at 15:48
• No, because I use the values of the integers as index. – Heslacher Dec 21 '16 at 15:52
• @Heslacher The problem with this answer is that negative numbers, and numbers greater than ~500million will break it. – 410_Gone Dec 22 '16 at 18:28

### Can be done in $O(n \log n)$ time and $O(1)$ space

I'm a little late to this question, but so far no one has come up with a better solution than $O(n^2)$ time and $O(1)$ space.

If you simply use a heapsort, which uses $O(1)$ space, you can achieve $O(n \log n)$ time as well. Heapsort is an in-place sort, but unlike quicksort it is not recursive, so it doesn't use $O(\log n)$ space. Also, it is quite simple - my version is only about 25 lines or so. I ran it with a 10 million element array and it finished in 2.56 seconds. Maybe someone can benchmark it versus the other solutions.

### Sample heapsort solution

using System;

class sort
{
static void Heap_PushDown(int [] heap, int heapSize, int parent)
{
int child = parent + parent + 1;

while (child < heapSize) {
if (child + 1 < heapSize && heap[child + 1] > heap[child])
child = child + 1;
if (heap[parent] >= heap[child])
break;

int tmp      = heap[parent];
heap[parent] = heap[child];
heap[child]  = tmp;
parent       = child;
child        = parent + parent + 1;
}
}

static Tuple<int, int> GetItemWithMaxCount(int[] items)
{
int heapSize = items.Length;

// Build the initial heap.
for (int i = heapSize / 2; i >= 0; i--) {
Heap_PushDown(items, heapSize, i);
}

// Do the heap sort.
while (heapSize > 0) {
int tmp         = items[0];
items[0]        = items[--heapSize];
items[heapSize] = tmp;
Heap_PushDown(items, heapSize, 0);
}

// Find the most common item in the sorted array.
int currentCount = 1;
int maxItem      = items[0];
int maxCount     = currentCount;
for (int i = 1; i < items.Length; i++) {
if (items[i] == items[i-1]) {
currentCount++;
if (currentCount > maxCount) {
maxItem  = items[i-1];
maxCount = currentCount;
}
} else {
currentCount = 1;
}
}

return new Tuple<int, int>(maxItem, maxCount);
}

static void Main(string[] args)
{
Random rand = new Random();
int size = 10000000;
int[] values = new int[size];
for (int i = 0; i < size; i++)
{
values[i] = rand.Next(size);
}
Tuple<int, int> t = GetItemWithMaxCount(values);
System.Console.WriteLine(t.Item1);
System.Console.WriteLine(t.Item2);
}
}

• Quicksort can be made to run in O(n lg n) time and O(1) space using an exact median subalgorithm, but it's true that the constant factor would probably be quite a bit more than the heapsort. – Peter Taylor Jan 5 '17 at 13:06
• @PeterTaylor Practically speaking, even a regular quicksort would only need a fixed stack of say, 64 elements because that would allow you to sort $2^{64}$ elements, which is an amount larger than the number of atoms in the universe. This assumes you always push the larger partition on the stack first. To achieve true $O(1)$ space yes you would need to do what you said and find the exact median so you could deduce the previous range from the smaller range. – JS1 Jan 5 '17 at 17:54
• Actually since the input is an array it can't have more than $2^{32}$ elements. Very good point. – Peter Taylor Jan 6 '17 at 22:30

OP relaxed the LINQ constraint
This is fresh code as existing code is all LINQ
Pretty sure this in O(n) in time and O(n) in space
It fails on the O(1) space but it will be the best time (I think)
Many of the posted LINQ solutions I think are not O(1) space

public static MostPoularItem FindMostPopularElement(int[] integers)
{
if (integers.Count() == 0)
throw new ArgumentOutOfRangeException();
//Dictionary<int, int> dic = new Dictionary<int, int>(integers.Count()/2);
Dictionary<int, int> dic = new Dictionary<int, int>();
foreach(int i in integers)
{
if(dic.Keys.Contains(i))
dic[i]++;
else
}
KeyValuePair<int, int> mpi = dic.OrderByDescending(x => x.Value)
.ThenBy(x => x.Key)
.FirstOrDefault();
return new MostPoularItem(mpi.Key, mpi.Value);
}


this is a faster version of EWbrown but on my machine mine is still faster at an array size of 10,000 and the O(n*n) just dies at 100,000

public static MostPoularItem GetItemWithMaxCountB(int[] items)
{
int maxCount = 0;
int maxItem = 0;
int currentItem;
int itemsLength = items.Length;

for (int i = 0; i < itemsLength - 1; i++)
{
if (maxCount > itemsLength - i)
break;
currentItem = items[i];
if (currentItem == maxItem)
continue;
var currentCount = 1;

for (int j = i + 1; j < items.Length; j++)
{
if (items[j] == currentItem)
{
currentCount++;
}
else if (maxCount > currentCount + itemsLength - i)
{
break;
}
}
if (currentCount > maxCount)
{
maxCount = currentCount;
maxItem = currentItem;
}
else if (currentCount == maxCount & currentItem < maxItem)
{
maxItem = currentItem;
}
}
return new MostPoularItem(maxItem, maxCount);
}

• Thanks! there are a few things that I would like to touch on. first: you are creating a dictionary and doing the book keeping inside it. That dictionary size will differ depending on the size of the input. So, it must be O(N) space, no? second thing: you create the dictionary by setting it's capacity to half of the input's size. How are you sure that it will not exceed that capacity as there are no assurance that input will only have unique values. – tugberk Dec 21 '16 at 15:13
• @tugberk If Dictionary exceeds that then it will grow. I was wrong this will NOT be O(1) space. – paparazzo Dec 21 '16 at 15:15
• Nice solution, it's also how I'd do it in Python. – Peilonrayz Dec 22 '16 at 19:10