LeetCode Entry

1535. Find the Winner of an Array Game

05.11.2023 medium 2023 kotlin

Find maximum of the k nearest in array

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

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
  }