Find the Winner of an Array Game
01 · Problem
You are given an array arr of distinct integers and an integer k.
A game is played on the array. Each round compares arr[0] and arr[1]: the larger value wins the round and stays at the front (position 0), while the smaller value is moved to the end of the array. The game ends as soon as some value wins k rounds in a row.
Return the value that wins the game. A winner always exists: once the maximum element reaches the front it never loses again.
02 · Examples
arr = [2,1,3,5,4,6,7], k = 2
5
Round 1: 2 beats 1. Round 2: 3 beats 2 (3's streak is 1). Round 3: 5 beats 3. Round 4: 5 beats 4, giving 5 two consecutive wins.
arr = [3,2,1], k = 10
3
3 is the maximum and is already at the front, so it wins every round and eventually reaches 10 wins.
arr = [1,9,8,2,3,7,6,4,5], k = 7
9
9 beats 1 and then beats 8, 2, 3, 7, 6, 4, reaching 7 wins in a row.
03 · Constraints
- 012 <= arr.length <= 105
- 021 <= arr[i] <= 106
- 03All values in arr are distinct
- 041 <= k <= 109
04 · Optimal complexity
- Time
- O(n)
- Space
- O(1)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.