LeetCode 486 Predict the Winner - Implementation

Here's the full solution:

function predictTheWinner(nums)
    n := length of nums
    dp := 2D (two-dimensional) array of size n × n
    // Base case: single elements
    for i := 0 to n - 1
        dp[i][i] := nums[i]
    // Fill for increasing lengths
    for length := 2 to n
        for i := 0 to n - length
            j := i + length - 1
            takeLeft := nums[i] - dp[i + 1][j]
            takeRight := nums[j] - dp[i][j - 1]
            dp[i][j] := max(takeLeft, takeRight)
    return dp[0][n - 1] >= 0

The outer loop iterates by subarray length. Each length, we try all starting positions $i$, compute the ending position $j = i + \text{length} - 1$, and fill $dp[i][j]$ using already-computed smaller subarrays. This keeps dependencies are satisfied.

Time: $O(n^2)$. Space: $O(n^2)$.

Time: $O(n^2)$. Space: $O(n^2)$.