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 initializationwins = -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
}