LeetCode Entry

1140. Stone Game II

26.05.2023 medium 2023 kotlin

While Alice and Bob optimally take 1..2 m numbers from piles find maximum for Alice.

1140. Stone Game II medium blog post substack

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/224

Problem TLDR

While Alice and Bob optimally take 1..2*m numbers from piles find maximum for Alice.

Intuition

For each position, we can cache the result for Alice starting from it. Next round, Bob will become Alice and use that cached result, but Alice will use the remaining part: \(bob_i = suffix_i - alice_i\) and \(alice_i = \sum(piles_{1..x<2m}) + (suffix_i - alice_{i + 1})\)

Approach

• compute prefix sums in IntArray
• use HashMap for simpler code, or Array for faster

  Complexity

• Time complexity: \(O(n^2)\)
• Space complexity: \(O(n^2)\)

Code

fun stoneGameII(piles: IntArray): Int {
    // 2 7 9 4 4    M      A   B
    // A            1      1
    // A A          2      2,7
    // A B B        2          7,9
    // A A B B B    3          9,4,4
    val sums = IntArray(piles.size)
    sums[0] = piles[0]
    for (i in 1..piles.lastIndex)
    sums[i] = sums[i - 1] + piles[i]
    val total = sums[sums.lastIndex]
    val cache = mutableMapOf<Pair<Int, Int>, Int>()
    fun dfs(m: Int, curr: Int): Int {
        return cache.getOrPut(m to curr) {
            var res = 0
            var pilesSum = 0
            for (x in 0 until 2*m) {
                if (curr + x > piles.lastIndex) break
                pilesSum += piles[curr + x]
                val nextOther = dfs(maxOf(m, x + 1), curr + x + 1)
                val nextMy = total - sums[curr + x] - nextOther
                res = maxOf(res, pilesSum + nextMy)
            }
            res
        }
    }
    return dfs(1, 0)
}