LeetCode Entry

1561. Maximum Number of Coins You Can Get

24.11.2023 medium 2023 kotlin

Get sum of second maxes of triples from array

1561. Maximum Number of Coins You Can Get medium blog post substack youtube image.png

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] }