🚀 96.74% || Simulation Game || Explained Intuition 🚀
Problem Description\n\nGiven an array of distinct integers, arr, and an integer k. A game is played between the first two elements of the array, arr[0] and arr[
# Problem Description\n\nGiven an array of distinct integers, `arr`, and an integer `k`. A game is played between the first **two** elements of the array, `arr[0]` and `arr[1]`. In each round, the **larger** integer remains at position `0`, while the smaller integer is **moved** to the **end** of the array. The game **continues** until one integer wins `k` consecutive rounds. \nThe task is to determine which integer will **win** the game. You can assume that there will **always** be a winner in the game.\n\n- **Constraints:**\n    - $2 <= arr.length <= 10^5$\n    - $1 <= arr[i] <= 10^6$\n    - arr contains **distinct** integers.\n    - $1 <= k <= 10^9$\n\n\n---\n\n\n\n# Intuition\n\nHi there, \uD83D\uDE04\n\nLet\'s zoom in\uD83D\uDD0E the details of our problem today.\n\nThe problem is that there is some kind of **games\uD83C\uDFAE** between the numbers of the given array. Each round, the first **two** elements play against eachothers and the **larger** -winner- stays in the position `0` in the array and the **smaller** -loser- goes to the **end** of the array. The winner of the whole game is who wins for `k` **consecutive** round.\nThe task is to find this **winner**.\uD83E\uDD47\n\nSeems cool!\uD83D\uDE0E\n\nDo you have any solutions in mind\uD83E\uDDE0 to solve it?\uD83E\uDD14\nActually, I have one. First thing I thought of was "Why not to **simulate** the game ?". Seems fair enough.\uD83D\uDE4C\n\nBut how can we simulate it ?\uD83E\uDD14\nThere many kind of techniques, One of them is for each element in the array we can let him play `k` rounds or until it **loses**. Unfortunately this solution will  give us **TLE** since it will have complexity of $O(N * K)$.\uD83D\uDE22\n\nAnother way to play the simulation ?\nLet\'s see some examples.\n\n```\nEX1 : arr = [2, 1, 7, 3, 4, 5], k = 3\n\nRound1 : winner = 2\narr = [2, 7, 3, 4, 5, 1]\n\nRound2 : winner = 7\narr = [7, 3, 4, 5, 1, 2]\n\nRound3 : winner = 7\narr = [7, 4, 5, 1, 2, 3]\n\nRound4 : winner = 7\narr = [7, 5, 1, 2, 3, 4]\n\nWinner of game = 7\n```\n```\nEX2 : arr = [2, 1, 7, 3], k = 4\n\nRound1 : winner = 2\narr = [2, 7, 3, 1]\n\nRound2 : winner = 7\narr = [7, 3, 1, 2]\n\nRound3 : winner = 7\narr = [7, 1, 2, 3]\n\nRound4 : winner = 7\narr = [7, 2, 3, 1]\n\nRound5 : winner = 7\narr = [7, 3, 1, 2]\n\nWinner of game = 7\n```\n\nDid you **noticed** something in the last two examples ?\uD83E\uDD14\nActually **YES** \uD83E\uDD29! `7` was the winner in the both games. \nIsn\'t `7` is the **largest** element in the these games ?\uD83E\uDD28\nAlso, **YES** !\n\nDo we have an **observation** here ?\uD83E\uDD2F\nAnother **YES**, whenever we encounter the **largest** element as the current winner then we are sure that he will when all the games since no other element is larger than it. \uD83D\uDCAA\n\nAnd we can also be sure of the winner of the game before even start it, HOW ?\uD83E\uDD2F\nSimply if `k` is larger than or equal to array size then the largest element is the winner since in such **games** the winner should defeat all other elements to **win** `k` games and the **only** element can do this is the **largest** element in the array.\n\nGood ! now we have **two** important **observations**. What will we do if the winner of the game **isn\'t** the largest element? How will we get it ?\uD83E\uDD14\nWe can **simulate** the game by tracking the winner and see the current **streak** of his wins and if the current winner has **won** `k` games -from the rules of the game- or it was the **largest** element in our array then it is the winner of the whole game.\uD83E\uDD47  \n\nBut wait, can\'t we **simulate** the game from the beggining **without** considering the **largest** element of the array ?\uD83E\uDD14\nSadly, Since $1 <= k <= 10^9$ and $2 <= arr,length <= 10^5$ then if we simulated the game until one element will when for `k` rounds only we will have **TLE**\uD83D\uDE14 so for that we will have to consider the largest element in our calculations.\n\n\n\nAnd this is the solution for our today\'S problem I hope that you understood it\uD83D\uDE80\uD83D\uDE80\n\n---\n\n\n# Approach\n\n1. Find the **maximum** element in the given integer array.\n2. Check if the value of `k` is **greater** than or equal to the size of the array.\n    - If **true**, return the **maximum** element, as it\'s the winner and no other element can **defeat** it.\n3. **Initialize** the `current winner` with the **first** element of the array and set the `current streak` to `0`.\n4. Iterate through the array starting from the second element (index 1):\n    - Compare the `current winner` with the next element.\n    - If the `current winner` is greater, increment the `current streak`.\n    - If the next element is greater, reset the streak to 1 and update the `current winner` to the new element.\n    - Check if the `current streak` has reached \'k\' or if the `current winner` is the maximum element.\n    - If **true**, return the `current winner` as the winner of the game.\n5. The return statement is **dummy** since it can\'t be reached.\n\n## Complexity\n- **Time complexity:**$O(N)$\nSince we are finding the **maximum** element in **linear** time `O(N)` and we are **iterating** over all elements in the array also in **linear** time `O(N)` so the total complexity is `O(N)`.\n- **Space complexity:**$O(1)$\nSince we are using **constant** variables.\n\n\n\n---\n\n\n\n# Code\n\n```C++ []\nclass Solution {\npublic:\n    int getWinner(vector<int>& arr, int k) {\n        // Find the maximum element in the array.\n        int maxElement = *max_element(arr.begin(), arr.end()); \n\n        // If k is greater than or equal to the array size, the maximum element wins.\n        if (k >= arr.size())\n            return maxElement; \n\n        int current_winner = arr[0]; // Initialize the current winner with the first element of the array.\n        int current_streak = 0; // Initialize the current streak to 0.\n\n        for (int i = 1; i < arr.size(); i++) {\n            // If the current winner is greater than the next element, then he will win the next game.\n            if (current_winner > arr[i])\n                current_streak++; \n\n            // the current winner lost the game.\n            else {\n                current_streak = 1; // Reset the streak since new element becomes the winner.\n                current_winner = arr[i]; // Update the current winner.\n            }\n\n            // If the current streak reaches k or the current winner is the maximum element\n            if (current_streak == k || current_winner == maxElement)\n                return current_winner; \n        }\n\n        return current_winner; // Dummy return\n    }\n};\n\n```\n```Java []\nclass Solution {\n    public int getWinner(int[] arr, int k) {\n        // Find the maximum element in the array.\n        int maxElement = Arrays.stream(arr).max().getAsInt();\n\n        // If k is greater than or equal to the array size, the maximum element wins.\n        if (k >= arr.length) {\n            return maxElement;\n        }\n\n        int currentWinner = arr[0]; // Initialize the current winner with the first element of the array.\n        int currentStreak = 0; // Initialize the current streak to 0.\n\n        for (int i = 1; i < arr.length; i++) {\n            // If the current winner is greater than the next element, then they will win the next game.\n            if (currentWinner > arr[i]) {\n                currentStreak++;\n\n            // the current winner lost the game.\n            } else {\n                currentStreak = 1; // Reset the streak since a new element becomes the winner.\n                currentWinner = arr[i]; // Update the current winner.\n            }\n\n            // If the current streak reaches k or the current winner is the maximum element\n            if (currentStreak == k || currentWinner == maxElement) {\n                return currentWinner;\n            }\n        }\n\n        return currentWinner; // Dummy return\n    }\n}\n```\n```Python []\nclass Solution:\n    def getWinner(self, arr, k):\n        # Find the maximum element in the list.\n        max_element = max(arr)\n        \n        # If k is greater than or equal to the list size, the maximum element wins.\n        if k >= len(arr):\n            return max_element\n        \n        current_winner = arr[0]  # Initialize the current winner with the first element of the list.\n        current_streak = 0  # Initialize the current streak to 0.\n        \n        for i in range(1, len(arr)):\n            # If the current winner is greater than the next element, then they will win the next game.\n            if current_winner > arr[i]:\n                current_streak += 1\n\n            # the current winner lost the game.\n            else:\n                current_streak = 1  # Reset the streak since a new element becomes the winner.\n                current_winner = arr[i]  # Update the current winner.\n            \n            # If the current streak reaches k or the current winner is the maximum element\n            if current_streak == k or current_winner == max_element:\n                return current_winner\n        \n        return current_winner  # Dummy return\n```\n```C []\nint getWinner(int* arr, int arrSize, int k) {\n    // Find the maximum element in the array.\n    int maxElement = arr[0];\n    for (int i = 1; i < arrSize; i++) {\n        if (arr[i] > maxElement) {\n            maxElement = arr[i];\n        }\n    }\n\n    // If k is greater than or equal to the array size, the maximum element wins.\n    if (k >= arrSize) {\n        return maxElement;\n    }\n\n    int current_winner = arr[0]; // Initialize the current winner with the first element of the array.\n    int current_streak = 0; // Initialize the current streak to 0.\n\n    for (int i = 1; i < arrSize; i++) {\n        // If the current winner is greater than the next element, then they will win the next game.\n        if (current_winner > arr[i]) {\n            current_streak++;\n\n        // the current winner lost the game.\n        } else {\n            current_streak = 1; // Reset the streak since a new element becomes the winner.\n            current_winner = arr[i]; // Update the current winner.\n        }\n\n        // If the current streak reaches k or the current winner is the maximum element\n        if (current_streak == k || current_winner == maxElement) {\n            return current_winner;\n        }\n    }\n\n    return current_winner; // Dummy return\n}\n```\n\n![HelpfulJerry.jpg](https://assets.leetcode.com/users/images/a4f85fd1-f8c4-4989-acae-da9459fe81e0_1699151064.0867484.jpeg)\n\n\n
['Array', 'C', 'Simulation', 'Python', 'C++', 'Java', 'Python3']