Find The First Player to Win K Games in a Row (LeetCode)

Problem statement:

You are given an array skills of integers, where skills[i] represents the skill level of the i-th player. Players are standing in a line and starting from the first player, each player competes with the next player. The player with the higher skill level wins the game. If two players have the same skill level, the first player wins.

A player who wins the game continues to compete with the next player in the line. The first player to win k consecutive games is declared the winner. If no player wins k consecutive games, return the player with the highest skill level at the end of the line.

You are asked to determine the index of the first player who wins k consecutive games.

Example 1:

Input: skills = [2, 1, 3, 5, 4, 6, 7], k = 2
Output: 5

Explanation: Player at index 5 wins 2 consecutive games (6 vs 4 and 6 vs 7).

Example 2:

Input: skills = [3, 2, 1], k = 10
Output: 0

Explanation: No player wins 10 consecutive games, so return the index of the player with the highest skill level (index 0).

Constraints:

• 1 <= skills.length <= 10^5
• 1 <= skills[i] <= 10^9
• 1 <= k <= skills.length

Solutions:

Approach:

We will simulate the process where each player competes with the next player in the array. We keep track of the number of consecutive wins for the current player. If the number of wins for the current player reaches k, we return the index of the current player.

Code:

Python

 class Solution:
   # Similar to 1535. Find the Winner of an Array Game
   def findWinningPlayer(self, skills: List[int], k: int) -> int:
     ans = 0
     wins = 0

     i = 1
     while i < len(skills) and wins < k:
       if skills[i] > skills[ans]:
         ans = i
         wins = 1
       else:
         wins += 1
       i += 1

     return ans

Java

 class Solution {
   // Similar to 1535. Find the Winner of an Array Game
   public int findWinningPlayer(int[] skills, int k) {
     int ans = 0;
     int wins = 0;

     for (int i = 1; i < skills.length && wins < k; ++i)
       if (skills[i] > skills[ans]) {
         ans = i;
         wins = 1;
       } else {
         ++wins;
       }

     return ans;
   }
 }

C++

  class Solution {
   public:
    // Similar to 1535. Find the Winner of an Array Game
    int findWinningPlayer(vector<int>& skills, int k) {
      int ans = 0;
      int wins = 0;

      for (int i = 1; i < skills.size() && wins < k; ++i)
        if (skills[i] > skills[ans]) {
          ans = i;
          wins = 1;
        } else {
          ++wins;
        }

      return ans;
    }
  };

Complexity Analysis:

Time Complexity:

The time complexity of this approach is $O(n)$, where $n$ is the number of players in the skills array. This is because each player is compared once.

Space Complexity:

The space complexity of this approach is $O(1)$ since we are using a constant amount of extra space.