[C++] O(n) | Two - Pointers |
Takeaways : \n- If maximum element is encountered, return that.\n- Keep the count of times an element wins.\n- Use two poiniters to iterate through the array\n\
Takeaways : \n- If maximum element is encountered, return that.\n- Keep the count of times an element wins.\n- Use two poiniters to iterate through the array\n\nTime : `O(n)`\nSpace : `O(max(arr[i]))` (because of the counter implementation using vector)\n```\nclass Solution {\npublic:\n    int getWinner(vector<int>& arr, int k) {\n        int p1 = 0, p2 = 1, r;\n        int mx = *max_element(arr.begin(), arr.end());\n        vector<int> wins(mx+1, 0);\n        int c = 0;\n        while(c != arr.size()-1) {\n            if (arr[p1] == mx || arr[p2] == mx) return mx;\n            if (arr[p1] > arr[p2]) {\n                wins[arr[p1]]++;\n                if (wins[arr[p1]] >= k) return arr[p1];\n                p2++;\n            } else {\n                wins[arr[p2]]++;\n                if (wins[arr[p2]] >= k) return arr[p2];\n                r = p2+1;\n                p1 = p2;\n                p2 = r;\n            }\n            c++;\n        }\n        return mx;\n    }\n};\n```
['Two Pointers', 'C']