C++/Python 1 loop vs deque||30ms Beats 100%
Intuition\n Describe your first thoughts on how to solve this problem. \nIf k>=len(arr) return max(arr)\n# Approach\n Describe your approach to solving the prob
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIf k>=len(arr) return max(arr)\n# Approach\n<!-- Describe your approach to solving the problem. -->\nOtherwise use a loop to proceed.\n\n`getWinner` finds the `winner` in an array by iterating through it and keeping track of the maximum value and the `count` of consecutive wins. If the count of consecutive wins reaches `k`, it returns the current `winner`. If the length of the array is less than or equal to k, it returns the maximum value in the array as the winner.\n\n2nd approach is for simulation using deque which is also fast runs in 54ms & beats 98.61%\n# Simulation for testcase\nConsider `arr=[1,8,2,3,7,6,4,5,9] k=8`\n```\nwinner=1 q:[8,2,3,7,6,4,5,9] cout=0\nwinner=8 q:[2,3,7,6,4,5,9,1] cout=1\nwinner=8 q:[3,7,6,4,5,9,1,2] cout=2\nwinner=8 q:[7,6,4,5,9,1,2,3] cout=3\nwinner=8 q:[6,4,5,9,1,2,3,7] cout=4\nwinner=8 q:[4,5,9,1,2,3,7,6] cout=5\nwinner=8 q:[5,9,1,2,3,7,6,4] cout=6\nwinner=8 q:[9,1,2,3,7,6,4,5] cout=7\nwinner=9 q:[1,2,3,7,6,4,5,8] cout=1\nwinner=9 q:[2,3,7,6,4,5,8,1] cout=2\nwinner=9 q:[3,7,6,4,5,8,1,2] cout=3\nwinner=9 q:[7,6,4,5,8,1,2,3] cout=4\nwinner=9 q:[6,4,5,8,1,2,3,7] cout=5\nwinner=9 q:[4,5,8,1,2,3,7,6] cout=6\nwinner=9 q:[5,8,1,2,3,7,6,4] cout=7\nwinner=9 q:[8,1,2,3,7,6,4,5] cout=8\n```\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(1)$$\ndeque method $$O(n)$$\n![30ms.png](https://assets.leetcode.com/users/images/fd743166-544b-4b5a-8240-8991b92c59d9_1699145659.4324698.png)\n\n# Code 30ms beats 100%\n```\nclass Solution {\npublic:\n    int getWinner(vector<int>& arr, int k) {\n        int n=arr.size();\n        if (n<=k) return *max_element(arr.begin(), arr.end());\n        int count=0, winner=arr[0];\n        #pragma unroll\n        for (int i=1; i<n && count<k; i++) {\n            if (arr[i] > winner) {\n                winner=arr[i];\n                count=1;\n            } \n            else \n                count++;\n        }\n        return winner;\n    }\n};\nauto init = []()\n{ \n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```\n# Python Code with Explanation in comments\n```\n# Define a class called Solution.\nclass Solution:\n    # Define a method called getWinner that takes an array \'arr\' and an integer \'k\' as inputs.\n    def getWinner(self, arr: List[int], k: int) -> int:\n        # Calculate the length of the input array and store it in \'n\'.\n        n = len(arr)\n        \n        # Check if the length of the array is less than or equal to \'k\'.\n        if n <= k:\n            # If so, return the maximum value in the array as the winner.\n            return max(arr)\n        \n        # Initialize variables to keep track of the count of consecutive wins and the current winner.\n        count = 0\n        winner = arr[0]\n        \n        # Iterate through the elements of the array starting from the second element.\n        for x in arr[1:]:\n            # Check if the current element \'x\' is greater than the current winner.\n            if x > winner:\n                # If \'x\' is greater, update the winner to \'x\' and reset the count to 1.\n                winner = x\n                count = 1\n            else:\n                # If \'x\' is not greater, increment the count.\n                count += 1\n            \n            # Check if the count has reached \'k\'.\n            if count == k:\n                # If so, break out of the loop.\n                break\n        \n        # Return the winner after the loop completes.\n        return winner\n\n```\n# C++ code using deque for simulation runs in 54ms & beats 98.61%\n```\n#pragma GCC optimize("O3")\nclass Solution {\npublic:\n    int getWinner(vector<int>& arr, int k) {\n        int n=arr.size();\n        if (n<=k) return *max_element(arr.begin(), arr.end());\n        deque<int> q(arr.begin()+1, arr.end());\n        int count=0, winner=arr[0];\n        while(count<k){\n            int x=q.front();\n            if (x>winner){\n                q.push_back(winner);\n                winner=x;\n                count=1;\n                q.pop_front();\n            }\n            else{\n                count++;\n                q.pop_front();\n                q.push_back(x);\n            }\n        }\n        return winner;\n    }\n};\nauto init = []()\n{ \n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```
['Queue', 'Simulation', 'C++', 'Python3']