Find the Winner of an Array Game solution and explanation
9 more videos on this problem
Find the Winner of an Array Game | Simulation | Easy Explanation | GOOGLE | Leetcode - 1535codestorywithMIK · 25:28 · 4K views
find the winner of an array game leetcode | leetcode 1535 | mediumNaresh Gupta · 7:25 · 4K views
LeetCode 1535. Find the Winner of an Array Game - Interview Prep Ep 86Fisher Coder · 9:57 · 1K views
1535. Find the Winner of an Array Game || Complete IntuitionAryan Mittal · 11:28 · 1K views
Leetcode | 1535. Find the Winner of an Array Game | Medium | Java SolutionDeveloper Docs · 6:38 · 850 views
Daily Leetcode #1314: Nov 05, 2023 - 1535. Find the Winner of an Array GameProgramming Live with Larry · 11:21 · 402 views
Find the Winner of an Array Game - Leetcode 1535 - PythonTechError · 3:43 · 258 views
1535. Find the Winner of an Array Game (Leetcode Medium)Programming Live with Larry · 6:04 · 236 views
Solving LeetCode 1535 Find the Winner of an Array Game | Google Interview QuestionCode Harmony · 10:09 · 228 views
Find the Winner of Array Game | Leetcode Weekly Contest 200 (1535) | Visual Editorial using DequeThe Algorithmic Eye · 1:56 · 184 views
The problem
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.
Constraints:
2 <= arr.length <= 1051 <= arr[i] <= 106arrcontains distinct integers.1 <= k <= 109
Approach overview
Problem Overview: You are given an integer array where the first two elements compete in rounds. The larger value wins and stays at the front, while the smaller moves to the end. The first number that wins k consecutive rounds becomes the winner. The task is to simulate this process and return the winning element.
Approach 1: Simulated Rounds Approach (O(n * k) time, O(n) space)
This method directly simulates the rules of the game using a queue-like process. Compare the first two elements, move the smaller value to the end, and keep the larger value at the front while tracking consecutive wins. Each round performs constant operations but can repeat many times if k is large. A queue or simple array rotation can model the process. This approach mirrors the problem description exactly and is useful for understanding the mechanics of the game.
Approach 2: Break Condition Approach (O(n) time, O(1) space)
The key observation is that the largest number in the array will eventually dominate every comparison. Instead of fully simulating rotations, iterate once through the array while maintaining a current champion and its consecutive win count. If the next value is larger, it becomes the new champion and the streak resets. Otherwise the champion's win streak increases. Once the streak reaches k, you can stop early. If no element reaches k, the maximum element of the array becomes the winner by default.
This approach works because the champion only changes when a larger element appears, which can happen at most n times. It avoids repeated array rotations and keeps only two variables: the current winner and win count.
Recommended for interviews: The Break Condition Approach is what interviewers typically expect. It shows you recognized the core insight that the maximum element will eventually dominate and that full simulation is unnecessary. Mentioning the simulated approach first demonstrates understanding of the game rules, while optimizing to the linear scan shows algorithmic reasoning. The problem mainly tests understanding of array traversal and efficient simulation patterns commonly used in competitive coding.
Approach 1: Simulated Rounds Approach
This approach involves simulating the game as described. In each round, compare the first two elements. The larger element stays at the front, while the smaller one is moved to the end. Track the number of consecutive wins for the current maximum element. The game terminates once an element wins k consecutive games, or we can conclude the maximum element will always win once it has dominated for enough rounds due to its magnitude relative to other elements.
def get_winner(arr, k):
max_num = arr[0]
win_count = 0
for num in arr[1:]:
if max_num > num:
win_count += 1
else:
max_num = num
win_count = 1
if win_count == k:
return max_num
return max_num
arr = [2, 1, 3, 5, 4, 6, 7]
k = 2
print("Winner:", get_winner(arr, k))class Solution {
public int getWinner(int[] arr, int k) {
int max = arr[0];
int winCount = 0;
for (int i = 1; i < arr.length; ++i) {
if (max > arr[i]) {
winCount++;
} else {
max = arr[i];
winCount = 1;
}
if (winCount == k) return max;
}
return max;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] arr = {2, 1, 3, 5, 4, 6, 7};
int k = 2;
System.out.println("Winner: " + sol.getWinner(arr, k));
}
}#include <vector>
#include <iostream>
using namespace std;
int getWinner(vector<int>& arr, int k) {
int max = arr[0];
int win_count = 0;
for (size_t i = 1; i < arr.size(); ++i) {
if (max > arr[i]) {
++win_count;
} else {
max = arr[i];
win_count = 1;
}
if (win_count == k)
return max;
}
return max;
}
int main() {
vector<int> arr{2, 1, 3, 5, 4, 6, 7};
int k = 2;
cout << "Winner: " << getWinner(arr, k) << endl;
return 0;
}function getWinner(arr, k) {
let max = arr[0];
let winCount = 0;
for (let i = 1; i < arr.length; i++) {
if (max > arr[i]) {
winCount++;
} else {
max = arr[i];
winCount = 1;
}
if (winCount === k) return max;
}
return max;
}
const arr = [2, 1, 3, 5, 4, 6, 7];
const k = 2;
console.log("Winner:", getWinner(arr, k));#include <stdio.h>
int getWinner(int* arr, int arrSize, int k) {
int max = arr[0];
int win_count = 0;
for (int i = 1; i < arrSize; ++i) {
if (max > arr[i]) {
win_count++;
} else {
max = arr[i];
win_count = 1;
}
if (win_count == k)
return max;
}
return max;
}
int main() {
int arr[] = {2, 1, 3, 5, 4, 6, 7};
int k = 2;
int winner = getWinner(arr, 7, k);
printf("Winner: %d\n", winner);
return 0;
}using System;
public class Solution {
public int GetWinner(int[] arr, int k) {
int max = arr[0];
int winCount = 0;
foreach (var num in arr[1..]) {
if (max > num) {
winCount++;
} else {
max = num;
winCount = 1;
}
if (winCount == k) return max;
}
return max;
}
public static void Main() {
Solution sol = new Solution();
int[] arr = {2, 1, 3, 5, 4, 6, 7};
int k = 2;
Console.WriteLine($"Winner: {sol.GetWinner(arr, k)}");
}
}In this Python code, we maintain the current maximum and its consecutive winning streak. Iterate through each element, compare, and update if necessary. As soon as a number wins k consecutive rounds, return it as the winner.
Time Complexity: O(n), where n is the number of integers in the list.
Space Complexity: O(1) as it uses only fixed space.
Approach 2: Break Condition Approach
This variant uses a concept very similar to the simulation approach but adds a breaking condition for improved efficiency. It exploits the game's characteristics by noting if the current maximum wins continuously even before counting to k, it will naturally reach the conclusion. This allows early termination if the maximum element becomes apparent quickly.
def get_winner(arr, k):
max_num = arr[0]
win_count = 0
for i, num in enumerate(arr[1:], start=1):
if max_num > num:
win_count += 1
else:
max_num = num
win_count = 1
if win_count == k or len(arr) - i + win_count > len(arr):
return max_num
return max_num
arr = [2, 1, 3, 5, 4, 6, 7]
k = 2
print("Winner:", get_winner(arr, k))class Solution {
public int getWinner(int[] arr, int k) {
int max = arr[0];
int winCount = 0;
for (int i = 1; i < arr.length; ++i) {
if (max > arr[i]) {
winCount++;
} else {
max = arr[i];
winCount = 1;
}
if (winCount == k || arr.length - i <= winCount)
return max;
}
return max;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] arr = {2, 1, 3, 5, 4, 6, 7};
int k = 2;
System.out.println("Winner: " + sol.getWinner(arr, k));
}
}#include <vector>
#include <iostream>
using namespace std;
int getWinner(vector<int>& arr, int k) {
int max = arr[0];
int winCount = 0;
for (size_t i = 1; i < arr.size(); ++i) {
if (max > arr[i]) {
++winCount;
} else {
max = arr[i];
winCount = 1;
}
if (winCount == k || max == arr.size() - i)
return max;
}
return max;
}
int main() {
vector<int> arr{2, 1, 3, 5, 4, 6, 7};
int k = 2;
cout << "Winner: " << getWinner(arr, k) << endl;
return 0;
}function getWinner(arr, k) {
let max = arr[0];
let winCount = 0;
for (let i = 1; i < arr.length; i++) {
if (max > arr[i]) {
winCount++;
} else {
max = arr[i];
winCount = 1;
}
if (winCount === k || winCount > arr.length - i) return max;
}
return max;
}
const arr = [2, 1, 3, 5, 4, 6, 7];
const k = 2;
console.log("Winner:", getWinner(arr, k));#include <stdio.h>
int getWinner(int* arr, int arrSize, int k) {
int max = arr[0];
int win_count = 0;
for (int i = 1; i < arrSize; ++i) {
if (max > arr[i]) {
++win_count;
} else {
max = arr[i];
win_count = 1;
}
if (win_count == k || max == arrSize - i) // break condition
return max;
}
return max;
}
int main() {
int arr[] = {2, 1, 3, 5, 4, 6, 7};
int k = 2;
int winner = getWinner(arr, 7, k);
printf("Winner: %d\n", winner);
return 0;
}using System;
public class Solution {
public int GetWinner(int[] arr, int k) {
int max = arr[0];
int winCount = 0;
for (int i = 1; i < arr.Length; ++i) {
if (max > arr[i]) {
++winCount;
} else {
max = arr[i];
winCount = 1;
}
if (winCount == k || arr.Length - i <= winCount)
return max;
}
return max;
}
public static void Main() {
Solution sol = new Solution();
int[] arr = {2, 1, 3, 5, 4, 6, 7};
int k = 2;
Console.WriteLine($"Winner: {sol.GetWinner(arr, k)}");
}
}Enhancing Python code with strategic exit, it estimates remaining rounds against advantageous maximum, ceasing prematurely if ongoing dominance is logically assertable.
Time Complexity: O(n), encouraged by occasional shortened loops.
Space Complexity: O(1).
Approach 3: Quick Thinking
We notice that each time the first two elements of the array are compared, regardless of the result, the next comparison will always be between the next element in the array and the current winner. Therefore, if we have looped n-1 times, the final winner must be the maximum element in the array. Otherwise, if an element has won consecutively k times, then this element is the final winner.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Similar problems:
function getWinner(arr: number[], k: number): number {
let mx = arr[0];
let cnt = 0;
for (const x of arr.slice(1)) {
if (mx < x) {
mx = x;
cnt = 1;
} else {
++cnt;
}
if (cnt === k) {
break;
}
}
return mx;
}func getWinner(arr []int, k int) int {
mx, cnt := arr[0], 0
for _, x := range arr[1:] {
if mx < x {
mx = x
cnt = 1
} else {
cnt++
}
if cnt == k {
break
}
}
return mx
}Complexity comparison
| Approach | Complexity |
|---|---|
| Simulated Rounds Approach | Time Complexity: O(n), where n is the number of integers in the list. |
| Break Condition Approach | Time Complexity: O(n), encouraged by occasional shortened loops. |
| Quick Thinking | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulated Rounds Approach | O(n * k) | O(n) | When implementing the game rules exactly or demonstrating a straightforward simulation. |
| Break Condition Approach | O(n) | O(1) | Best for interviews and large inputs since it avoids repeated rotations and stops early when a champion reaches k wins. |
Frequently asked questions
Is Find the Winner of an Array Game easy or hard?
The problem is classified as Medium on LeetCode. The challenge is recognizing that full simulation is unnecessary and that the maximum element will eventually dominate comparisons, enabling a linear-time solution.
Find the Winner of an Array Game Python/Java solution
In Python or Java, maintain two variables: the current champion and its consecutive wins. Iterate through the array, update the champion when a larger element appears, and increment the win count otherwise. Stop once the streak equals k, producing an O(n) solution.
How to solve Find the Winner of an Array Game in O(n)?
Iterate through the array while maintaining a current winner and a consecutive win counter. When the next value is larger, replace the winner and reset the counter; otherwise increase the streak. Once the streak reaches k, return the winner. If no value reaches k wins, the maximum element becomes the result.
What is the best approach for Find the Winner of an Array Game?
The optimal solution uses a break-condition linear scan. Track the current champion and its consecutive win count while iterating through the array. If a larger element appears, it becomes the new champion and the streak resets. This approach runs in O(n) time and O(1) space.
Is Find the Winner of an Array Game asked at Google/Amazon/Meta?
Problems involving array simulation and maintaining a running champion appear frequently in interviews at companies like Amazon and Google. They test understanding of efficient iteration, early termination conditions, and recognizing when full simulation can be simplified.
What data structure is used in Find the Winner of an Array Game?
The problem primarily relies on arrays and simple counters. A queue-like structure can be used in the simulation approach, but the optimal solution only requires scanning the array while tracking the current maximum and win streak.
What is the time complexity of Find the Winner of an Array Game?
The optimal algorithm runs in O(n) time because each element is compared at most once while determining the current champion. Space complexity is O(1) since only the current winner and a counter are stored.