# 05.11.2023 [1535. Find the Winner of an Array Game]

Find maximum of the `k` nearest in array

05.11.2023

1535. Find the Winner of an Array Game medium
blog post

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/394

Problem TLDR

Find maximum of the k nearest in array

Intuition

Looking at some examples:

  // 0 1 2 3 4 5
  // 1 3 2 5 4 10            3
  //   3 2 5 4 10 1          3
  //   3   5 4 10 1 2        5
  //       5 4 10 1 2 3      5
  //       5   10 1 2 3 4    10
  //           10 1 2 3 4 5  10 ...

we can deduce that the problem is trivial when k >= arr.size - it is just a maximum.
Now, when k < arr.size we can just simulate the given algorithm and stop on the first k-winner.

Approach

• we can iterate over 1..arr.lastIndex or use a clever initialization wins = -1

Complexity

• Time complexity:
  O(n)

• Space complexity:
  O(1)

Code

  fun getWinner(arr: IntArray, k: Int): Int {
    var wins = -1
    var max = arr[0]
    for (x in arr) {
      if (x > max) {
        wins = 1
        max = x
      } else wins++
      if (wins == k) break
    }
    return max
  }