💯Faster✅💯 Lesser✅3 Methods🔥Simulation Approach🔥Dequeue🔥Two Pointer and Hashtable🔥LinkedList🔥
\uD83D\uDE80 Hi, I\'m Mohammed Raziullah Ansari, and I\'m excited to share 4 ways to solve this question with detailed explanation of each approach:\n\n# Proble
# \uD83D\uDE80 Hi, I\'m [Mohammed Raziullah Ansari](https://leetcode.com/Mohammed_Raziullah_Ansari/), and I\'m excited to share 4 ways to solve this question with detailed explanation of each approach:\n\n# Problem Description: \nWe are given an integer array arr containing distinct integers and an integer k. We need to determine the winner in a game played between the first two elements of the array, arr[0] and arr[1]. In each round of the game, We compare arr[0] with arr[1], and the larger integer wins. The winning integer stays in position 0, while the other integer is moved to the end of the array. The game continues until one integer wins k consecutive rounds, and We need to find the winning integer.\n\n# \uD83D\uDD0D Methods To Solve This Problem:\nI\'ll be covering four different methods to solve this problem:\n1. Simulation Approach\n2. Dequeue\n3. Two Pointer and Hashtable\n\n# 1. Simulation Approach: \n- Initialize $$currentWinner$$ to the first element of the array and $$count$$ to 0.\n- Iterate through the array from the second element to the end.\n- Compare the current element with $$currentWinner$$. If the current element is greater, update $$currentWinner$$ to the current element and reset $$count$$ to 1.\n- If the current element is not greater, increment $$count$$.\n- Check if $$count$$ equals $$k$$. If yes, return $$currentWinner$$.\n- Continue the loop until a winner is found.\n# Complexity\n- \u23F1\uFE0F Time Complexity: $$O(n)$$, where n is the size of the input array. This is because we iterate through the entire array once.\n\n- \uD83D\uDE80 Space Complexity: $$O(1)$$, as we use only a constant amount of extra space for variables.\n\n# Code\n```Python []\nclass Solution:\n    def getWinner(self, arr: List[int], k: int) -> int:\n        currentWinner = arr[0]\n        count = 0\n        for i in range(1, len(arr)):\n            if arr[i] > currentWinner:\n                currentWinner = arr[i]\n                count = 1\n            else:\n                count += 1\n            if count == k:\n                return currentWinner\n        return currentWinner\n```\n```Java []\nclass Solution {\n    public int getWinner(int[] arr, int k) {\n        int currentWinner = arr[0];\n        int count = 0;\n        for (int i = 1; i < arr.length; i++) {\n            if (arr[i] > currentWinner) {\n                currentWinner = arr[i];\n                count = 1;\n            } else {\n                count++;\n            }\n            if (count == k) {\n                return currentWinner;\n            }\n        }\n        return currentWinner;\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    int getWinner(vector<int>& arr, int k) {\n        int currentWinner = arr[0];\n        int count = 0;\n        for (int i = 1; i < arr.size(); i++) {\n            if (arr[i] > currentWinner) {\n                currentWinner = arr[i];\n                count = 1;\n            } else {\n                count++;\n            }\n            if (count == k) {\n                return currentWinner;\n            }\n        }\n        return currentWinner;\n    }\n};\n```\n```C []\nint getWinner(int* arr, int arrSize, int k) {\n    int currentWinner = arr[0];\n    int count = 0;\n    for (int i = 1; i < arrSize; i++) {\n        if (arr[i] > currentWinner) {\n            currentWinner = arr[i];\n            count = 1;\n        } else {\n            count++;\n        }\n        if (count == k) {\n            return currentWinner;\n        }\n    }\n    return currentWinner;\n}\n```\n# 2. Dequeue (Queue):\n- Initialize a queue $$q$$ with all elements of the array and $$one$$ to the first element.\n- Initialize $$x$$ to $$k$$, calculate the maximum value $$maxi$$ in the array.\n- If $$k$$ is greater than or equal to the array size, return $$maxi$$.\n- Enter a loop that continues while $$k$$ is greater than 0.\n- In each iteration, dequeue the next element $$two$$ from the queue.\n- Compare $$one$$ and $$two$$. If $$one$$ is greater, decrement $$k$$ and enqueue $$two$$. If $$two$$ is greater, reset $$k$$ to its original value $$x$$, decrement $$k$$, and enqueue $$one$$. Update $$one$$ to be $$two$$.\n- Continue the loop until $$k$$ consecutive wins are reached.\n- Return $$one$$ as the winner.\n# Complexity\n- \u23F1\uFE0F Time Complexity: $$O(n)$$, because we enqueue and dequeue each element once, and in the worst case, we iterate through the array twice.\n\n- \uD83D\uDE80 Space Complexity: $$O(n)$$, as we use a queue to store all the elements of the array.\n\n# Code\n```Python []\nfrom collections import deque\n\nclass Solution:\n    def getWinner(self, arr: List[int], k: int) -> int:\n        q = deque(arr)\n        one = q.popleft()\n        x = k\n        maxi = max(arr)\n        if k >= len(arr):\n            return maxi\n        while k:\n            two = q.popleft()\n            if one > two:\n                k -= 1\n                q.append(two)\n            else:\n                k = x\n                k -= 1\n                q.append(one)\n                one = two\n        return one\n```\n```Java []\nimport java.util.LinkedList;\nimport java.util.Queue;\n\nclass Solution {\n    public int getWinner(int[] arr, int k) {\n        Queue<Integer> q = new LinkedList<>();\n        for (int i : arr) {\n            q.offer(i);\n        }\n        int one = q.poll();\n        int x = k;\n        int maxi = Arrays.stream(arr).max().getAsInt();\n        if (k >= arr.length) {\n            return maxi;\n        }\n        while (k > 0) {\n            int two = q.poll();\n            if (one > two) {\n                k--;\n                q.offer(two);\n            } else {\n                k = x;\n                k--;\n                q.offer(one);\n                one = two;\n            }\n        }\n        return one;\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    int getWinner(vector<int>& arr, int k) {\n        queue<int> q;\n        for (auto i : arr) {\n            q.push(i);\n        }\n        int one = q.front();\n        q.pop();\n        int x = k;\n        int maxi = *max_element(arr.begin(), arr.end());\n        if (k >= arr.size()) {\n            return maxi;\n        }\n        while (k) {\n            int two = q.front();\n            q.pop();\n            if (one > two) {\n                k--;\n                q.push(two);\n            } else {\n                k = x;\n                k--;\n                q.push(one);\n                one = two;\n            }\n        }\n        return one;\n    }\n};\n```\n```C []\nint getWinner(int* arr, int arrSize, int k) {\n    int* queue = (int*)malloc(arrSize * sizeof(int));\n    int one = arr[0];\n    int x = k;\n    int maxi = arr[0];\n    for (int i = 1; i < arrSize; i++) {\n        queue[i - 1] = arr[i];\n        if (arr[i] > maxi) {\n            maxi = arr[i];\n        }\n    }\n    if (k >= arrSize) {\n        free(queue);\n        return maxi;\n    }\n    int* newQueue = (int*)malloc(arrSize * sizeof(int));\n    while (k) {\n        int two = queue[0];\n        for (int i = 0; i < arrSize - 1; i++) {\n            queue[i] = queue[i + 1];\n        }\n        if (one > two) {\n            k--;\n            queue[arrSize - 1] = two;\n        } else {\n            k = x;\n            k--;\n            queue[arrSize - 1] = one;\n            one = two;\n        }\n    }\n    free(queue);\n    return one;\n}\n```\n# 3. Two Pointer and Hashtable:\n- Initialize a dictionary $$d$$ to keep track of wins for each integer and two pointers, $$i$$ and $$j$$, to traverse the array.\n- Enter a loop that continues as long as both $$i$$ and $$j$$ are within the array\'s bounds.\n- Compare $$arr[i]$$ and $$arr[j]$$.\n- Update the wins in the dictionary $$d$$ accordingly, and advance the pointers.\n- If $$arr[i]$$ is greater, increment $$i$$. If $$arr[j]$$ is greater, update $$i$$ to be $$j$$ and reset the wins for $$arr[i]$$.\n- Continue the loop until $$k$$ consecutive wins are reached.\n- Return the winner, which is $$arr[i]$$.\n# Complexity\n- \u23F1\uFE0F Time Complexity: $$O(n)$$, because we iterate through the entire array once with the two pointers.\n\n- \uD83D\uDE80 Space Complexity: $$O(n)$$, as we use a dictionary d to store the wins for each integer, which could have n distinct elements.\n\n# Code\n```Python []\nclass Solution:\n    def getWinner(self, arr: List[int], k: int) -> int:\n        n = len(arr)\n        d = {i: 0 for i in arr}\n        i, j = 0, 1\n        while i < n and j < n:\n            if arr[i] > arr[j]:\n                d[arr[i]] += 1\n            elif arr[i] < arr[j]:\n                d[arr[j]] += 1\n                i = j\n            if d[arr[i]] == k:\n                return arr[i]\n            j += 1\n        return max(arr)\n```\n```Java []\nclass Solution {\n    public int getWinner(int[] arr, int k) {\n        int n = arr.length;\n        HashMap<Integer, Integer> wins = new HashMap<>();\n        int i = 0, j = 1;\n        while (i < n && j < n) {\n            if (arr[i] > arr[j]) {\n                wins.put(arr[i], wins.getOrDefault(arr[i], 0) + 1);\n            } else if (arr[i] < arr[j]) {\n                wins.put(arr[j], wins.getOrDefault(arr[j], 0) + 1);\n                i = j;\n            }\n            if (wins.get(arr[i]) == k) {\n                return arr[i];\n            }\n            j++;\n        }\n        int maxVal = Arrays.stream(arr).max().getAsInt();\n        return maxVal;\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    int getWinner(vector<int>& arr, int k) {\n        int n = arr.size();\n        unordered_map<int, int> wins;\n        int i = 0, j = 1;\n        while (i < n && j < n) {\n            if (arr[i] > arr[j]) {\n                wins[arr[i]]++;\n            } else if (arr[i] < arr[j]) {\n                wins[arr[j]]++;\n                i = j;\n            }\n            if (wins[arr[i]] == k) {\n                return arr[i];\n            }\n            j++;\n        }\n        int maxVal = *max_element(arr.begin(), arr.end());\n        return maxVal;\n    }\n};\n```\n```C []\nint getWinner(int* arr, int arrSize, int k) {\n    int* wins = (int*)malloc(arrSize * sizeof(int));\n    for (int i = 0; i < arrSize; i++) {\n        wins[i] = 0;\n    }\n    int i = 0;\n    int j = 1;\n    while (i < arrSize && j < arrSize) {\n        if (arr[i] > arr[j]) {\n            wins[i]++;\n        } else if (arr[i] < arr[j]) {\n            wins[j]++;\n            i = j;\n        }\n\n        if (wins[i] == k) {\n            free(wins);\n            return arr[i];\n        }\n        j++;\n    }\n    int maxVal = arr[0];\n    for (int i = 1; i < arrSize; i++) {\n        if (arr[i] > maxVal) {\n            maxVal = arr[i];\n        }\n    }\n    free(wins);\n    return maxVal;\n}\n```\n# \uD83C\uDFC6Conclusion: \nThe optimal approach among the three presented methods would be the "Dequeue (Queue)" approach (Approach 2). This approach efficiently utilizes a queue to simulate the game, making it possible to achieve the result with fewer iterations, which can be particularly useful for large input arrays.\n\n# \uD83D\uDCA1 I invite We to check out my profile for detailed explanations and code for each method. Happy coding and learning! \uD83D\uDCDA
['Array', 'Hash Table', 'Linked List', 'Two Pointers', 'C', 'Simulation', 'C++', 'Java', 'Python3']