# 24.11.2023 [1561. Maximum Number of Coins You Can Get]
Get sum of second maxes of triples from array
24.11.2023
1561. Maximum Number of Coins You Can Get medium
blog post
youtube
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/415
Problem TLDR
Get sum of second maxes of triples from array
Intuition
Observing the example:
// 1 2 3 4 5 6 7 8 9
// * * * 8
// * * * 6
// * * * 4
// size = x + 2x
we can deduce an optimal algorithm: give bob the smallest value, and take the second largest. There are exactly size / 3
moves total.
Approach
Let’s write it in a functional style, using Kotlin’s API:
sorted
drop
chunked
sumBy
Complexity
Time complexity:
O(nlog(n))Space complexity:
O(n), can be O(1) when sorted in-place
Code
fun maxCoins(piles: IntArray): Int =
piles.sorted()
.drop(piles.size / 3)
.chunked(2)
.sumBy { it[0] }