Smallest element in an array that is repeated exactly ‘k’ times

Question

This is a problem from GeeksForGeeks and I have tried to solve it on my own and I have written this code.

Given an array of size n, the goal is to find out the smallest number that is repeated exactly ‘k’ times where k > 0? Assume that array has only positive integers and 1 <= arr[i] < 1000 for each i = 0 to n -1.

Examples:

Input:

arr[] = {2 2 1 3 1}
k = 2

Output: 1

Explanation:

Here in array:

• 2 is repeated 2 times
• 1 is repeated 2 times
• 3 is repeated 1 time

Hence 2 and 1 both are repeated 'k' times

i.e 2 and min(2, 1) is 1

Input:

arr[] = {3 5 3 2}
k = 1

Output: 2

Explanation:

Both 2 and 5 are repeating 1 time but min(5, 2) is 2

How can I improve this code?

#include <iostream>
#include <vector>
#include <map>

template<class T>
void findElement(std::vector<T>& vec, int k)
{
  std::map<T, int> count;
  for(T x : vec)
  {
    count[x]++;
  }

  typename std::map<T, int>::iterator itr;
  for(itr = count.begin(); itr != count.end(); itr++)
  {
    if(itr->second == k)
    {
      std::cout << itr->first <<'\n';
      return;
    }
  }
  std::cerr << "No such element \n ";
}

int main()
{
  std::vector<char> v;
  v.push_back('r');
  v.push_back('t');
  v.push_back('q');
  v.push_back('r');
  v.push_back('u');
  v.push_back('q');
  v.push_back('s');
  int k;
  std::cout << " Enter the number of repetitions you want : ";
  std::cin >> k;
  std::cout << "The smallest element that has " << k <<" reptition is : ";
  findElement(v, k);
}

Answer 1

Interface

• There's no point in limiting your function inputs to a vector. You can take two input iterators instead. It'll make your function more flexible and more "standard library-like".

• One function should do one focused thing. Your function finds such an element and prints it as the same time. These concerns are unrelated. You can return std::optional<T> instead to represent either such an element or its absence. Note: it works for C++17 only. You can use boost::optional or return a smart pointer if it's not available.

Modern C++

• There's no need for things like this anymore:

  typename std::map<T, int>::iterator itr;
  for(itr = count.begin(); itr != count.end(); itr++)
  

  for (const auto& kv : count) is much better, isn't it?

• You can also use initialization list to create a vector with the elements you need: std::vector<char> v({'r', 't',..., 's'})

Performance

• for (T x : vec) creates an unnecessary copy. Use for (const T& x : vec) or for (const auto& T : vec) instead.

• You can also use std::unordered_map to do the counting and then choose the smallest element (it's more efficient because one can find the minimum in O(n). It's "easier" than sorting the input). One caveat: you need a hash function for T in this case. You can pass it as another template parameter, defaulted to std::hash.

Answer 2

Looking at the problem statement, a few obvious solutions come to mind:

1. Count of many of each number there is and take the smallest with 'k' entries. This is what you do and as you are using a std::map with log(m) insertion where 'm' is the number of distinct elements (bounded by 1000) so you have \$O(n\log(m))\$ run time and \$O(m)\$ memory.
2. Sort the input vector and scan linearly from the start until you find something that repeats 6 times. As you have to sort the whole thing you get \$O(nlogn)\$ time and \$O(n)\$ memory unless you can modify the input array.

But there is a better way:

/**
 * Will find the smallest value in 'vec' that is repeated 'k' times.
 *
 * It is assumed that values of 'vec' are [1, 1000[ as per 
 * problem description. 
 */
void findElement(const std::vector<unsigned int>& vec, int k){
  constexpr auto max_value = 1000U;
  std::array<unsigned int, max_value> freq;
  freq.fill(k);
  for(auto& value : vec){
      freq.at(value)--;
  }
  for(std::size_t f = 0; f < freq.size(); ++f){
      if(0 == freq[f]){
          std::cout << f <<'\n';
          return;
      }
  }
  std::cerr << "No such element\n";
}

The raw array is actually faster as this code only performs \$O(n+m)\$ work which is less than \$O(nlogm)\$. Yes it's not as "generic" as the template method and won't work for all T. But it doesn't need to be able to do that for the task.

One could solve this using std::unordered_map as well, and the big O time is the same:

template<typename Container>
void findElement(const Container& container, int k){
    std::unordered_map<Container::value_type, int> freq;
    for(auto& value : container){
        freq[value]++;
    }
    auto smallest = freq.end();
    for(auto& entry : freq){
        if(entry.second == k && (smallest != freq.end() || entry.first < smallest.first )){
            smallest = entry;
        }
    }

    if(smallest != freq.end()){
        std::cout << smallest.first <<'\n';
    }
    else{
        std::cerr << "No such element\n";¨
    }
}

The algorithm is essentially the same with one minor difference, the approach with the std::unordered_map may not terminate early on finding the first element with exactly 'k' occurrences as the array based algorithm can. This means that the unordered_map version must visit exactly all 'M<1000' unique values in 'vec' including some overhead from traversing a sparse hash-map, while the array version on average only needs to visit '1000/2' of the possible values.

So they have different cases where they are faster. For example a degenerate case such as K=3 , {999,999,999} is faster with unordered_map as you only visit one unique element but with the array solution you need to (very quickly) scan through the 998 elements in the array. But on average on random sets the array solution is expected to be slightly faster by a constant factor as both have the same big O time.