Practice/Amazon/Leetcode 1535. Find the Winner of an Array Game

Leetcode 1535. Find the Winner of an Array Game

CodingOptional

Problem

You are given an array of distinct integers and an integer k. The array participates in a tournament game with the following rules:

• Compare the first two elements of the array
• The larger element "wins" the round and stays at the front
• The smaller element "loses" and moves to the back of the array
• Keep track of how many consecutive rounds the current front element has won
• The tournament ends when an element wins k consecutive rounds

Return the integer that wins k consecutive rounds.

Important observation: If k is greater than or equal to the array length, the maximum element in the array will always win, since it will beat every other element at least once.

Requirements

1. Return the first element to achieve k consecutive wins
2. Handle cases where k exceeds the array size
3. Ensure the solution terminates efficiently without simulating unnecessary rounds

Constraints

• 2 ≤ arr.length ≤ 105
• 1 ≤ arr[i] ≤ 106
• All integers in arr are distinct
• 1 ≤ k ≤ 109
• Expected time complexity: O(n)
• Expected space complexity: O(1)

Examples

Example 1:

Input: arr = [2, 1, 3, 5, 4, 6, 7], k = 2 Output: 5 Explanation: Round 1: 2 vs 1 → 2 wins (consecutive wins: 1), arr becomes [2, 3, 5, 4, 6, 7, 1] Round 2: 2 vs 3 → 3 wins (consecutive wins: 1), arr becomes [3, 5, 4, 6, 7, 1, 2] Round 3: 3 vs 5 → 5 wins (consecutive wins: 1), arr becomes [5, 4, 6, 7, 1, 2, 3] Round 4: 5 vs 4 → 5 wins (consecutive wins: 2), 5 reaches k=2 wins

Example 2:

Input: arr = [3, 2, 1], k = 10 Output: 3 Explanation: 3 is the maximum element and will beat all others. Since k=10 exceeds the array size, the maximum element 3 will win.

Example 3:

Input: arr = [1, 9, 8, 2, 3], k = 3 Output: 9 Explanation: Round 1: 1 vs 9 → 9 wins (consecutive wins: 1) Round 2: 9 vs 8 → 9 wins (consecutive wins: 2) Round 3: 9 vs 2 → 9 wins (consecutive wins: 3) 9 achieves k=3 consecutive wins.