Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1535.html
1535. Find the Winner of an Array Game (Medium)
Given an integer array arr
of distinct integers and an integer k
.
A game will be played between the first two elements of the array (i.e. arr[0]
and arr[1]
). In each round of the game, we compare arr[0]
with arr[1]
, the larger integer wins and remains at position 0
and the smaller integer moves to the end of the array. The game ends when an integer wins k
consecutive rounds.
Return the integer which will win the game.
It is guaranteed that there will be a winner of the game.
Example 1:
Input: arr = [2,1,3,5,4,6,7], k = 2 Output: 5 Explanation: Let's see the rounds of the game: Round  arr  winner  win_count 1  [2,1,3,5,4,6,7]  2  1 2  [2,3,5,4,6,7,1]  3  1 3  [3,5,4,6,7,1,2]  5  1 4  [5,4,6,7,1,2,3]  5  2 So we can see that 4 rounds will be played and 5 is the winner because it wins 2 consecutive games.
Example 2:
Input: arr = [3,2,1], k = 10 Output: 3 Explanation: 3 will win the first 10 rounds consecutively.
Example 3:
Input: arr = [1,9,8,2,3,7,6,4,5], k = 7 Output: 9
Example 4:
Input: arr = [1,11,22,33,44,55,66,77,88,99], k = 1000000000 Output: 99
Constraints:
2 <= arr.length <= 10^5
1 <= arr[i] <= 10^6
arr
contains distinct integers.1 <= k <= 10^9
Related Topics:
Array
Solution 1. Queue
Just simulate the process. Because once we visit the maximum number in the array, we’ll at most visit the entire array one more time, so the time complexity is O(N)
.
Note that if we found that one number has beaten other N  1
numbers already, we don’t need to continue the loop and this maximum number must be the result.
Actually just using a queue
is enough, but queue
doesn’t support initialization using queue<int> q(begin(A), end(A))
.
// OJ: https://leetcode.com/problems/findthewinnerofanarraygame/
// Time: O(N)
// Space: O(N)
class Solution {
public:
int getWinner(vector<int>& A, int k) {
deque<int> q(begin(A), end(A));
int N = A.size(), x = q.front(), cnt = 0;
q.pop_front();
while (cnt < k && cnt < N  1) {
int y = q.front();
q.pop_front();
if (x > y) {
++cnt;
q.push_back(y);
} else {
cnt = 1;
q.push_back(x);
x = y;
}
}
return x;
}
};
Solution 2. Monostack (Next Greater Element)
// OJ: https://leetcode.com/problems/findthewinnerofanarraygame/
// Time: O(N)
// Space: O(N)
class Solution {
public:
int getWinner(vector<int>& A, int k) {
int N = A.size();
if (k >= N  1) return *max_element(begin(A), end(A));
vector<int> next(N, 1);
stack<int> s; // decreasing monostack
for (int i = 0; i < 2 * N; ++i) {
while (s.size() && A[s.top() % N] < A[i % N]) {
next[s.top() % N] = i % N;
s.pop();
}
s.push(i);
}
for (int i = 0; i < N; ++i) {
if (next[i] == 1  next[i]  i  (i == 0) >= k) return A[i];
}
return 1;
}
};
Solution 3. One pass
One key observation is that after comparing all the elements first pass, we don’t need to compare the current winning element from the beginning of the array again because we must meet the greatest element in the first pass which will definitely win the game.
// OJ: https://leetcode.com/problems/findthewinnerofanarraygame/
// Time: O(N)
// Space: O(1)
// Ref: https://leetcode.com/problems/findthewinnerofanarraygame/discuss/768007/JavaC%2B%2BPythonOnePassO(1)Space
class Solution {
public:
int getWinner(vector<int>& A, int k) {
int cur = A[0], win = 0;
for (int i = 1; i < A.size(); ++i) {
if (A[i] > cur) {
cur = A[i];
win = 0;
}
if (++win == k) break;
}
return cur;
}
};

class Solution { public int getWinner(int[] arr, int k) { int prev = Math.max(arr[0], arr[1]); if (k == 1) return prev; int consecutive = 1; int max = prev; int length = arr.length; for (int i = 2; i < length; i++) { int curr = arr[i]; if (prev > curr) { consecutive++; if (consecutive == k) return prev; } else { prev = curr; consecutive = 1; } max = Math.max(max, curr); } return max; } } ############ class Solution { public int getWinner(int[] arr, int k) { int time = 0, max = arr[0]; for (int i = 1; i < arr.length; i++) { if (max > arr[i]) { time++; } else { time = 1; max = arr[i]; } if (time >= k) { return max; } } return max; } }

// OJ: https://leetcode.com/problems/findthewinnerofanarraygame/ // Time: O(N) // Space: O(N) class Solution { public: int getWinner(vector<int>& A, int k) { deque<int> q(begin(A), end(A)); int N = A.size(), x = q.front(), cnt = 0; q.pop_front(); while (cnt < k && cnt < N  1) { int y = q.front(); q.pop_front(); if (x > y) { ++cnt; q.push_back(y); } else { cnt = 1; q.push_back(x); x = y; } } return x; } };