1535. Find the Winner of an Array Game

Difficulty:
Related Topics:
Similar Questions:

    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:

    Solution

    /**
     * @param {number[]} arr
     * @param {number} k
     * @return {number}
     */
    var getWinner = function(arr, k) {
        var maxIndex = 0;
        for (var i = 1; i < arr.length; i++) {
            if (arr[i] > arr[maxIndex]) maxIndex = i;
            if (i - maxIndex + (maxIndex === 0 ? 0 : 1) === k) break;
        }
        return arr[maxIndex];
    };
    

    Explain:

    We keep track of the maximum number index while iterating the array, in index i, the maximum number wined i - maxIndex + 1 times (or i - maxIndex times if maxIndex is zero)

    Complexity: