Boyer-Moore majority vote algorithm + map
Intuition\n#### Boyer - Moore majority vote algorithm + map\nThe algorithm looks for a majority element, if one exists. Among the input elements, a majority ele
# Intuition\n#### Boyer - Moore majority vote algorithm + map\nThe algorithm looks for a majority element, if one exists. Among the input elements, a majority element is one that shows up more frequently than 50% of the time. The algorithm, however, will continue to output one of the items if there isn\'t a majority and won\'t recognize this.\n\nTwo sections make up the algorithm. An element that is supposedly a majority element is discovered in a first pass, and its majority status is then confirmed in a second pass.\n\n# Approach\n#### Algorithm\n\nIn order to keep track of a sequence element and a counter. The counter is started at zero at the beginning. After that, we iterate over the input elements. If the value of counter is zero while processing element x, the algorithm sets the counter to one and remembers x as a sequence element. If not, the value of counter is evaluated against the sequence element.\nWhen an element is found to be same as sequence element, the counter is increased; when it is not, the counter is decreased. Atlast we have our supposedly majority element that is sequence element.\nNow that we have a candidate majority element we can authenticate its majority element status in O(n) time complexity, incase the candidate is not a majority element then there exsits no majority element in the given input.\n\n\n**First Pass :**\n\nFinding a candidate with the majority in the first pass\n\n    - Set up the variables m and count with initial values of 0.\n    - For every xth component of the input sequence:\n    - If count is equal to zero, we set m to equal x and count to 1, otherwise we increase count if m is also equal to x.\n    - if not, we reduce the count.\n    - Lastly, give back the saved element m.\n\n**Second Pass :**\n\nChecking if the contender has more than n/2 votes on the second pass\n\n    - Set a variable\'s count initial value to zero.\n    - If an element is the same as a candidate, loop over the list of items and increase the count.\n    - Return the candidate if the count is larger than n/2\n\n#### Caching ranges\nWhen a query range is encountered, its value is evaluated and stored inside a map to reduce (in practice) runtime complexity in the event that another query runs with an identical range but a different threshold.\n\n\n# Complexity\n- Time complexity: $$O(n*q+q*log(q))$$\n<!-- Add your time complexity here, e.g.  -->\n\n- Space complexity: $$O(q)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n\n\nclass MajorityChecker {\n    vector<int>arr;\n    map<pair<int,int>,pair<int,int>>cache;\npublic:    \n    MajorityChecker(vector<int>& arr) {\n        this->arr=arr;\n    }\n    int query(int left, int right, int threshold) {\n        if(cache.find({left,right})!=cache.end()){\n            return cache[{left,right}].first>=threshold?cache[{left,right}].second:-1;\n        }\n        int element = -1;\n        int vote = 0;\n        for(int i=left;i<=right;i++){\n            if(!vote){\n                element = arr[i];\n            }\n            if(element == arr[i])\n                vote++;\n            else\n                vote--;\n        }\n        int count = 0;\n        for(int i = left; i<=right; i++){\n            if(arr[i] == element)\n                count++;\n        }\n        cache[{left,right}] = {count, element};\n        return count>=threshold?element:-1;\n    }\n};\n\n/**\n * Your MajorityChecker object will be instantiated and called as such:\n * MajorityChecker* obj = new MajorityChecker(arr);\n * int param_1 = obj->query(left,right,threshold);\n */\n```
['Array', 'Design', 'Ordered Map', 'C++']