Finding the most popular element with C# given O(1) space complexity requirement

Question

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.

Answer 1

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

Answer 2

    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.

Answer 3

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.

Answer 4

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>?)

Answer 5

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

Answer 6

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);
    }
}

Answer 7

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);
    //for space start with 0 - for speed integers.Count()/2
    Dictionary<int, int> dic = new Dictionary<int, int>();
    foreach(int i in integers)
    {
        if(dic.Keys.Contains(i))
            dic[i]++;
        else
            dic.Add(i, 1);
    }
    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);
}