Given some integers, return the k most frequent elements

Question

Given a non-empty array of integers, return the k most frequent elements.

For example, given [1,1,1,2,2,3] and k = 2, return [1,2].

Following is my submission to this problem on Leetcode and it is accepted. Can you please provide feedback on any issue that you see in this code? I am looking for improvements in the quality of the code from both software engineering perspective as well as from algorithmic complexity or space and run-time performance perspective.

#include <algorithm>
#include <map>
#include <vector>

using namespace std;


class Node
{
public:

    int value{};
    unsigned frequency{};

    Node()
    {

    }

    Node (int value, unsigned frequency)
    {
        this->value = value;
        this->frequency = frequency;
    }

    bool operator< (const Node& other)
    {
        return this->frequency < other.frequency;
    }
};

class Solution {
public:

    vector<int> topKFrequent(vector<int>& nums, int k) 
    {            
        map<int, unsigned> frequency;

        for (auto n : nums )
        {
            if ( frequency.find(n) != frequency.end())
                frequency[n]++;
            else
                frequency[n] = 0;
        }

        vector<Node> heap;

        for ( auto f : frequency )
            heap.push_back(Node(f.first, f.second));

        make_heap(heap.begin(), heap.end());

        vector<int> result;

        unsigned i = 0;
        while ( i < k )
        {  
            result.push_back(heap.front().value);
            pop_heap(heap.begin(), heap.end()-i);
            i++;
        }


        return result;
    }
};

Answer 1

Just the general C++ coding style treatment.

1. Do not use using namespace std;. It can introduce subtle bugs, makes the code harder to read and writing out the std:: prefix generally is not going to be to time intensive.

2. Keep your spacing consistent. Compare the following two lines

   bool operator< (const Node& other)
   vector<int> topKFrequent(vector<int>& nums, int k)
   

   Why is one method name followed by a space while the other is not? Consistency is important! If you are not sure which spacing variant to choose, you should read a C++ style guide. The same applies to control structures, such as

   for (auto n : nums )
   if ( frequency.find(n) != frequency.end())
   for ( auto f : frequency )
   

3. Use a member initializer list in your constructor. Although it does not matter in a lot of cases, it is a more concise way of expressing member initialization and leaves the constructor's body open for more complex setup tasks. The Node constructor would then look something like this:

   Node(int value, unsigned frequency) : value(value), frequency(frequency) { }
   

   Also, since you default constructor does not actually do anything, you should remove it and the initializers for value and frequency and add default values to the constructor parameters instead, so that Node's constructor becomes something like

   Node(int value = 0, unsigned frequency = 0) : value(value), frequency(frequency) { }
   

   Keep in mind, however, that this constructor allows implicit conversions from integer types, which you typically want to avoid. This is easily prevented by making the constructor explicit.

4. Most people prefer to not write this-> explicitly when not needed.

5. const-correctness is important. You should take the parameter nums in topKFrequent by const-reference since you do not actually modify it.
6. Always use curly brackets with if,else,for,while etc. This prevents a lot of errors from statements not being included in conditionally dependent blocks when they should be. In fact, this kind of error is so common that gcc even introduced a diagnostic for misleading indentation in version 6.

Answer 2

Algorithm

Let's look at the time complexity of the different parts of the implementation:

• Build a std::map of frequencies: \$O(n \log n)\$. This could be improved to \$O(n)\$ by using a hash map instead.
• Build a max-heap of the m unique elements: \$O(m \log m)\$
• Pop the top k items from the heap: \$O(k \log m)\$

If k is very small compared to m, then building a heap from the entire collection is overkill. It would be better to build a min-heap of k elements. That way, only k elements will be kept in heap order, instead of the larger m. The content of the heap will be the most frequent k elements.

If k is close to m, then popping k elements is overkill. It would be better to build a max-heap of m - k elements. The elements excluded from the heap will be the most frequent k elements.

Variable scope

It's good to limit variables to the smallest possible scope. For example here, the variable i is visible outside the loop, but it's only used inside:

unsigned i = 0;
while ( i < k )
{  
    result.push_back(heap.front().value);
    pop_heap(heap.begin(), heap.end()-i);
    i++;
}

It would be better to rewrite this as a for loop, that will make i visible only inside.

Program organization

Building the map of frequencies and then finding the k most frequent items are two independent steps. It would be good to put these steps in separate private functions.

Pair of values

Instead your custom Node, it would be better to use std::pair.

C++

I admit my C++ is pretty rusty, I was not able to get this code to compile using g++ or g++ -std=c++11 or g++ -std=c++14. I would like to think that it's possible to adjust this code so that it becomes trivial to compile.

Mainly I wanted to check if this part can be simplified:

int value{};
unsigned frequency{};

Node()
{

}

To this:

int value;
unsigned frequency;

Because an empty constructor and the {} after field declaration seem pointless, and I would like to code to be as simple as possible, with as little noise as possible.

Answer 3

An alternative approach would fully leverage the many standard algorithms and containers in the standard library. Here's one such mechanism:

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

int main()
{
    // test vector to demonstrate solution
    const std::vector<int> input{1,2,3,4,2,3,4,1,1,2,1,2,1,2,1,3,5};
    std::unordered_map<int, int> count;
    for (int i : input) {
        ++count[i];
    }
    std::vector<std::pair<int, int>> pairs;
    pairs.reserve(count.size());
    std::copy(count.begin(), count.end(), std::back_inserter(pairs));
    int k = 3;
    std::partial_sort(pairs.begin(), pairs.begin()+k, pairs.end(),
          [](const std::pair<int, int> &a, const std::pair<int, int> &b) {
                 return a.second > b.second;
           }
    );
    for (int i = 0; i < k; ++i) {
        std::cout << pairs[i].first << ", " << pairs[i].second << '\n';
    }
}

Output

The output to this sample program is the top k data items with their associated count:

1, 6
2, 5
3, 3

Key points:

Use unordered containers for efficiency

One can use either a std::map as you have done, or a std::unordered_map as in this code. The latter often confers a performance advantage when ordering is not needed, as in this application.

Use std::partial_sort

We can use std::partial_sort with a custom predicate to have the program only order the first k entries in the list. This can be faster than sorting the entire list when only a fraction of the list needs to be sorted.

Use std::copy where practical

Rather than copy the entries piece by piece, if you can use std::copy, it's both more clear to readers of the code and sometimes more efficient.

Use existing data structures where practical

The original code uses a custom Node class, but it's essentially no different from the std::pair<int, int> that is natively used by std::map and std::unordered_map.

Use reserve to avoid dynamically resizing

The revised code uses reserve to allocate exactly the number of items needed in the std::vector. This can save time and memory because it avoids reallocation and copying that happens when such data structures must be expanded as items are added.