✅ 98.37% O(n) Final Winner
Intuition\nWhen first approaching this problem, we might think about simulating the entire process: comparing numbers, moving the smaller one to the end, and ke
# Intuition\nWhen first approaching this problem, we might think about simulating the entire process: comparing numbers, moving the smaller one to the end, and keeping track of the number of consecutive wins. However, a closer inspection reveals a couple of key insights. Firstly, if the game needs only one win (i.e., $ k = 1 $), the winner of the first round is the answer. Secondly, if $ k $ is large enough (i.e., $ k $ is equal to or larger than the length of the array), the maximum element in the array is bound to win eventually. These initial observations allow us to build a strategy that handles these edge cases separately, providing an efficient approach for the main logic.\n\n# Live Coding & More\nhttps://youtu.be/cbFwAvhG_C8?si=ussPA9wySWxCxLp3\n\n# Approach\n1. **Edge Cases**: Check if $ k $ is 1 or if $ k $ is equal to or larger than the length of the array. These cases allow for immediate conclusions.\n2. **Initialization**: Initialize the current winner as the first element and set the consecutive wins count to zero.\n3. **Iteration**: Iterate through the array starting from the second element. For each element:\n   - If the current winner is greater, increment the consecutive win count.\n   - If the current element is greater, it becomes the new winner and the consecutive win count resets to 1.\n   - If at any point the consecutive win count reaches $ k $, the current winner is the answer.\n4. **Final Winner**: If the loop completes without finding an answer, the current winner after the loop is the answer.\n\nThis approach ensures that we only iterate through the list once, making the solution efficient.\n\n# Complexity\n\n- **Time complexity**: $ O(n) $\n  The solution iterates through the array once. In the worst-case scenario, we examine all elements in the array. Hence, the time complexity is linear with respect to the size of the array.\n\n- **Space complexity**: $ O(1) $\n  The solution uses a constant amount of extra space: a few variables to keep track of the current winner and the consecutive win count. Regardless of the size of the input, the space used remains constant.\n\n# Code\n``` Python []\nclass Solution:\n    def getWinner(self, arr: List[int], k: int) -> int:\n        if k == 1:\n            return max(arr[0], arr[1])\n        if k >= len(arr):\n            return max(arr)\n        \n        current_winner = arr[0]\n        consecutive_wins = 0\n        \n        for i in range(1, len(arr)):\n            if current_winner > arr[i]:\n                consecutive_wins += 1\n            else:\n                current_winner = arr[i]\n                consecutive_wins = 1\n            \n            if consecutive_wins == k:\n                return current_winner\n        \n        return current_winner\n```\n``` C++ []\nclass Solution {\npublic:\n    int getWinner(std::vector<int>& arr, int k) {\n        if (k == 1) {\n            return std::max(arr[0], arr[1]);\n        }\n        if (k >= arr.size()) {\n            return *std::max_element(arr.begin(), arr.end());\n        }\n\n        int current_winner = arr[0];\n        int consecutive_wins = 0;\n\n        for (int i = 1; i < arr.size(); ++i) {\n            if (current_winner > arr[i]) {\n                consecutive_wins++;\n            } else {\n                current_winner = arr[i];\n                consecutive_wins = 1;\n            }\n\n            if (consecutive_wins == k) {\n                return current_winner;\n            }\n        }\n\n        return current_winner;\n    }\n};\n```\n``` Java []\npublic class Solution {\n    public int getWinner(int[] arr, int k) {\n        if (k == 1) {\n            return Math.max(arr[0], arr[1]);\n        }\n        if (k >= arr.length) {\n            return Arrays.stream(arr).max().getAsInt();\n        }\n\n        int current_winner = arr[0];\n        int consecutive_wins = 0;\n\n        for (int i = 1; i < arr.length; i++) {\n            if (current_winner > arr[i]) {\n                consecutive_wins++;\n            } else {\n                current_winner = arr[i];\n                consecutive_wins = 1;\n            }\n\n            if (consecutive_wins == k) {\n                return current_winner;\n            }\n        }\n\n        return current_winner;\n    }\n}\n```\n``` C# []\npublic class Solution {\n    public int GetWinner(int[] arr, int k) {\n        if (k == 1) {\n            return Math.Max(arr[0], arr[1]);\n        }\n        if (k >= arr.Length) {\n            return arr.Max();\n        }\n\n        int current_winner = arr[0];\n        int consecutive_wins = 0;\n\n        for (int i = 1; i < arr.Length; i++) {\n            if (current_winner > arr[i]) {\n                consecutive_wins++;\n            } else {\n                current_winner = arr[i];\n                consecutive_wins = 1;\n            }\n\n            if (consecutive_wins == k) {\n                return current_winner;\n            }\n        }\n\n        return current_winner;\n    }\n}\n```\n``` Go []\npackage main\n\nfunc getWinner(arr []int, k int) int {\n    if k == 1 {\n        return max(arr[0], arr[1])\n    }\n    if k >= len(arr) {\n        return maxArr(arr)\n    }\n\n    current_winner := arr[0]\n    consecutive_wins := 0\n\n    for i := 1; i < len(arr); i++ {\n        if current_winner > arr[i] {\n            consecutive_wins++\n        } else {\n            current_winner = arr[i]\n            consecutive_wins = 1\n        }\n\n        if consecutive_wins == k {\n            return current_winner\n        }\n    }\n\n    return current_winner\n}\n\nfunc max(a, b int) int {\n    if a > b {\n        return a\n    }\n    return b\n}\n\nfunc maxArr(arr []int) int {\n    m := arr[0]\n    for _, val := range arr {\n        if val > m {\n            m = val\n        }\n    }\n    return m\n}\n```\n``` Rust []\nimpl Solution {\n    pub fn get_winner(arr: Vec<i32>, k: i32) -> i32 {\n        if k == 1 {\n            return arr[0].max(arr[1]);\n        }\n        if k as usize >= arr.len() {\n            return *arr.iter().max().unwrap();\n        }\n\n        let mut current_winner = arr[0];\n        let mut consecutive_wins = 0;\n\n        for &num in &arr[1..] {\n            if current_winner > num {\n                consecutive_wins += 1;\n            } else {\n                current_winner = num;\n                consecutive_wins = 1;\n            }\n\n            if consecutive_wins == k {\n                return current_winner;\n            }\n        }\n\n        current_winner\n    }\n}\n```\n``` PHP []\nclass Solution {\n    function getWinner($arr, $k) {\n        if ($k == 1) {\n            return max($arr[0], $arr[1]);\n        }\n        if ($k >= count($arr)) {\n            return max($arr);\n        }\n\n        $current_winner = $arr[0];\n        $consecutive_wins = 0;\n\n        for ($i = 1; $i < count($arr); $i++) {\n            if ($current_winner > $arr[$i]) {\n                $consecutive_wins++;\n            } else {\n                $current_winner = $arr[$i];\n                $consecutive_wins = 1;\n            }\n\n            if ($consecutive_wins == $k) {\n                return $current_winner;\n            }\n        }\n\n        return $current_winner;\n    }\n}\n```\n``` JavaScript []\n/**\n * @param {number[]} arr\n * @param {number} k\n * @return {number}\n */\nvar getWinner = function(arr, k) {\n        if (k === 1) {\n            return Math.max(arr[0], arr[1]);\n        }\n        if (k >= arr.length) {\n            return Math.max(...arr);\n        }\n\n        let current_winner = arr[0];\n        let consecutive_wins = 0;\n\n        for (let i = 1; i < arr.length; i++) {\n            if (current_winner > arr[i]) {\n                consecutive_wins++;\n            } else {\n                current_winner = arr[i];\n                consecutive_wins = 1;\n            }\n\n            if (consecutive_wins === k) {\n                return current_winner;\n            }\n        }\n\n        return current_winner;\n    }\n```\n\n# Performance\n| Language   | Execution Time (ms) | Memory Usage (MB) |\n|------------|---------------------|-------------------|\n| Java       | 3                   | 55.8              |\n| Rust       | 11                  | 3.4               |\n| JavaScript | 70                  | 51.6              |\n| C++        | 81                  | 63.5              |\n| Go         | 87                  | 8.2               |\n| C#         | 156                 | 53.8              |\n| PHP        | 186                 | 31.5              |\n| Python3    | 500                 | 29.6               |\n\n![v10.png](https://assets.leetcode.com/users/images/a812ec5b-de25-4ea9-808d-ced8b9e35f96_1699144577.2158473.png)\n\n\n# Conclusion\nUnderstanding the rules of the game and the implications of the value of $ k $ were crucial in devising this efficient solution. By handling edge cases separately, we were able to focus on the main logic without unnecessary complications. This problem demonstrates the importance of thoroughly analyzing the problem statement to identify key insights that can simplify the solution.
['Array', 'PHP', 'Simulation', 'C++', 'Java', 'Go', 'Python3', 'Rust', 'JavaScript', 'C#']