Leetcode 1535. Find the Winner of an Array Game

Problem Explanation

You’re given an array of distinct integers. A game is played between the first two elements and the winner stays at the first position and the loser is moved to the end of the array. This continues until an integer wins k consecutive rounds. The goal is to find this integer.

For example, consider the array [2,1,3,5,4,6,7] and k = 2. The rounds of the game will be as follows:

• Round 1: Array after the game [2,3,5,4,6,7,1]. Winner: 2.
• Round 2: Array after the game [3,5,4,6,7,1,2]. Winner: 3.
• Round 3: Array after the game [5,4,6,7,1,2,3]. Winner: 5.
• Round 4: Array after the game [5,4,6,7,1,2,3]. Winner: 5.

Here 5 has won 2 consecutive rounds. Therefore, it is the winner and the function should return 5.

Approach

This problem can be solved using a simple iterative approach. Start a for loop from the second element of the array. The first element is considered the current winner with a win streak of 0. If the current element is greater than the current winner, it becomes the new winner with a win streak of 1. If the current element is less than the current winner, the win streak of the current winner is incremented by 1. The loop continues until the win streak is less than k.

Python Solution

1
2python
3class Solution:
4    def getWinner(self, arr: List[int], k: int) -> int:
5        current = arr[0]
6        win_count = 0
7        for i in range(1, len(arr)):
8            if arr[i] > current:
9                current = arr[i]
10                win_count = 1
11            else:
12                win_count += 1
13            if win_count == k:
14                break
15        return current

Java Solution

1
2java
3class Solution {
4    public int getWinner(int[] arr, int k) {
5        int current = arr[0];
6        int win_count = 0;
7        for (int i=1; i<arr.length; i++) {
8            if (arr[i] > current) {
9                current = arr[i];
10                win_count = 1;
11            } else {
12                win_count++;
13            }
14            if (win_count == k) {
15                break;
16            }
17        }
18        return current;
19    }
20}

Javascript Solution

1
2javascript
3class Solution {
4    getWinner(arr, k) {
5        let current = arr[0];
6        let win_count = 0;
7        for (let i=1; i<arr.length; i++) {
8            if (arr[i] > current) {
9                current = arr[i];
10                win_count = 1;
11            } else {
12                win_count++;
13            }
14            if (win_count == k) {
15                break;
16            }
17        }
18        return current;
19    }
20}

C++ Solution

1
2cpp
3class Solution {
4public:
5    int getWinner(vector<int>& arr, int k) {
6        int current = arr[0];
7        int win_count = 0;
8        for (int i=1; i<arr.size(); i++) {
9            if (arr[i] > current) {
10                current = arr[i];
11                win_count = 1;
12            } else {
13                win_count++;
14            }
15            if (win_count == k) {
16                break;
17            }
18        }
19        return current;
20    }
21};

C# Solution

1
2csharp
3public class Solution {
4    public int GetWinner(int[] arr, int k) {
5        int current = arr[0];
6        int win_count = 0;
7        for (int i=1; i<arr.Length; i++) {
8            if (arr[i] > current) {
9                current = arr[i];
10                win_count = 1;
11            } else {
12                win_count++;
13            }
14            if (win_count == k) {
15                break;
16            }
17        }
18        return current;
19    }
20}

Notes

The complexity of the solution is O(n), as it potentially iterates over the whole array exactly once. The memory complexity is O(1) as it doesn't use any extra memory.The above solution body mainly consists on brute forcing the solution by linearly looping over the array and checking the win condition at each step. They all have a time complexity of O(n). It works fine for smaller arrays since it doesn't require any additional space, but as arrays get larger, the time it requires to find the result increases linearly.

A tweak can be made to reduce the time complexity even further, by noting that if 'k' is larger than or equal to the length of the array, then the maximum element in the array will always win regardless of its position. By making this observation, one can decrease the number of iterations hence making the solution more efficient for larger lists. Here is the improved code snippet in Python, JavaScript and Java respectively.

Python Improved Solution:

1
2python
3class Solution:
4    def getWinner(self, arr: List[int], k: int) -> int:
5        current = arr[0]
6        win_count = 0
7        if k >= len(arr):
8            return max(arr)
9        for i in range(1, len(arr)):
10            if arr[i] > current:
11                current = arr[i]
12                win_count = 1
13            else:
14                win_count += 1
15            if win_count == k:
16                break
17        return current

JavaScript Improved Solution:

1
2javascript
3class Solution {
4    getWinner(arr, k) {
5        let current = arr[0];
6        let win_count = 0;
7        if (k >= arr.length) {
8            return Math.max(...arr);
9        }
10        for (let i=1; i< arr.length; i++) {
11            if (arr[i] > current) {
12                current = arr[i];
13                win_count = 1;
14            } else {
15                win_count++;
16            }
17            if (win_count == k) {
18                break;
19            }
20        }
21        return current;
22    }
23}

Java Improved Solution:

1
2java
3class Solution {
4    public int getWinner(int[] arr, int k) {
5        int current = arr[0];
6        int win_count = 0;
7        if (k >= arr.length) {
8            Arrays.sort(arr);
9            return arr[arr.length-1];
10        }
11        for (int i=1; i<arr.length; i++) {
12            if (arr[i] > current) {
13                current = arr[i];
14                win_count = 1;
15            } else {
16                win_count++;
17            }
18            if (win_count == k) {
19                break;
20            }
21        }
22        return current;
23    }
24}

These solutions have an average time complexity closer to O(n), with the worst case being O(n log n) due to the added sorting step. However, for many inputs, this approach will yield significant performance improvements over the brute force method by early returning when the game is guaranteed to be won by the maximum element.