LeetCode Entry

1406. Stone Game III

03.08.2026 hard 2026 kotlin rust

Pick up to 3 from the left to win game

1406. Stone Game III hard substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1440

Problem TLDR

Pick up to 3 from the left to win game

Intuition

Dp of a choice: pick one, two or three. Cached by the tail of the array.

Approach

• rewrite into bottom-up: itertate from the tail, remember last 3

Complexity

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

• Space complexity: \(O(1)\)

Code

    fun stoneGameIII(s: IntArray) = listOf("Bob", "Tie", "Alice")[
        s.foldRight(IntArray(5)) { x, (a, b, c, u, v) ->
            intArrayOf(maxOf(x - a, x + u - b, x + u + v - c), a, b, x, u)
        }[0].sign + 1
    ]

    pub fn stone_game_iii(s: Vec<i32>) -> String {
        ["Bob", "Tie", "Alice"][(s.into_iter().rfold([0; 5], |[a, b, c, u, v], x| {
            [(x - a).max(x + u - b).max(x + u + v - c), a, b, x, u]
        })[0].signum() + 1) as usize].into()
    }