LeetCode Entry

1406. Stone Game III

27.05.2023 hard 2023 kotlin

Winner of “Alice”, “Bob” or “Tie” in game of taking 1, 2 or 3 stones by turn from stoneValue array.

1406. Stone Game III hard blog post substack

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/225

Problem TLDR

Winner of “Alice”, “Bob” or “Tie” in game of taking 1, 2 or 3 stones by turn from stoneValue array.

Intuition

Let’s count the result for Alice, starting at i element: \(alice_i = \sum_{i=1,2,3}(stones_i) + suffix_i - alice_{i+1}\) The result can be safely cached. Bob’s points will be Alice’s points in the next turn.

Approach

Let’s write bottom up DP.

• use increased sizes for cache and suffix arrays for simpler code
• corner case is the negative number, so we must take at least one stone

  Complexity

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

Code

fun stoneGameIII(stoneValue: IntArray): String {
    val suffix = IntArray(stoneValue.size + 1)
    for (i in stoneValue.lastIndex downTo 0) suffix[i] = stoneValue[i] + suffix[i + 1]
    val cache = IntArray(stoneValue.size + 1)
    var bob = 0

    for (curr in stoneValue.lastIndex downTo 0) {
        var sum = 0
        var first = true
        for (j in 0..2) {
            val ind = curr + j
            if (ind > stoneValue.lastIndex) break
            sum += stoneValue[ind]
            val nextAlice = cache[ind + 1]
            val next = suffix[ind + 1] - nextAlice
            if (first || sum + next > cache[curr]) {
                first = false
                cache[curr] = sum + next
                bob = nextAlice
            }
        }
    }
    return if (cache[0] == bob) "Tie" else if (cache[0] > bob) "Alice" else "Bob"
}