LeetCode Entry

486. Predict the Winner

01.08.2026 medium 2026 kotlin rust

Optimal choices to win

486. Predict the Winner medium substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1438

Problem TLDR

Optimal choices to win

Intuition

DFS: take the left or take the right; add to your sum, your tail is the total sum - opponent sum

Approach

• problem is small, no need for dp
• even size: player 1 always wins

Complexity

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

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

Code

    fun predictTheWinner(n: IntArray): Boolean {
        fun d(from:Int, to:Int): Int = if (from==to) n[from]
        else max(n[from]-d(from+1,to), n[to]-d(from,to-1))
        return n.size%2<1 || d(0,n.size-1)>=0
    }

    pub fn predict_the_winner(n: Vec<i32>) -> bool {
        let mut d = [0;21];
        for i in 0..n.len() { for j in (0..=i).rev() {
            d[j]=(n[i]-d[j]).max(n[j]-d[j+1])
        }}; d[0] >= 0
    }