algo: More than one third

/*105 Answers
Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time ( n >=0 )

You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo

- shondik on June 27, 2012 in India | Report Duplicate 

*/
/**
First step is to find the candicates. There are at most two candidates, each with more than n/3 appearance.
Like Tetris, every time you have 3 different elements in a group, you delete them all. At last, the remaining elements are the candidates with more than n/3 appearance. Due to peogen hole principle, the candicates are at least one element more than the non-candidates.

One round to find the candidates.
Second round to verify the candidates. Overall complexity O(n).
*/

#include <map>
#include <array>
#include <iostream>
#include <vector>
using namespace std;
template <typename T>
class Solution{
public:
  vector<T> getOverOneThird(vector<T> const& element_array){
    vector<T> result;
    map<T, int> counter;
    for(int ii = 0; ii < element_array.size(); ++ii){
      if (counter.size() == 3){//level full, delete or decrement
        for(auto it = counter.begin(); it != counter.end();){
          if (it->second > 0){
            --it->second;
            ++it;
          }
          else counter.erase(it++);
        }//for it
      }//if  counter.size()==3
      ++counter[element_array[ii]];
    }//for ii
    //now in counter, only the candidates survived
    for(auto it = counter.begin(); it != counter.end(); ++it){//init
      it->second = 0;
    }
    for(int ii = 0; ii < element_array.size(); ++ii){//verify the candidates
      for(auto it = counter.begin(); it != counter.end(); ++it){//counting
        T element = it->first;
        if (element_array[ii] == element) ++it->second;
      }
    }
    for(auto it = counter.begin(); it != counter.end(); ++it){//verified
      if (3 * it->second > element_array.size()) result.push_back(it->first);
    }
    return result;
  }//getOverOneThird
};

int main(){
  cout<<"Hello"<<endl;
  array<int, 12> a = {1,1,1,1,1,2,2,2,2,2,3,3};
  vector<int> elements(a.begin(), a.end());
  Solution<int> s;
  vector<int> output = s.getOverOneThird(elements);
  for(int ii = 0 ; ii < output.size(); ++ii){
    cout<<output[ii]<<endl;
  }
}