Predict the Winner - Practice Coding Problems

Predict the Winner - Problem

Array Math Dynamic Programming Recursion Game Theory Medium

You are given an integer array nums. Two players are playing a game with this array: player 1 and player 2.

Player 1 and player 2 take turns, with player 1 starting first. Both players start the game with a score of 0. At each turn, the player takes one of the numbers from either end of the array (i.e., nums[0] or nums[nums.length - 1]) which reduces the size of the array by 1. The player adds the chosen number to their score.

The game ends when there are no more elements in the array. Return true if Player 1 can win the game. If the scores of both players are equal, then player 1 is still the winner, and you should also return true. You may assume that both players are playing optimally.

Input & Output

Example 1 — Player 1 Wins

$ Input: nums = [1,5,2]

› Output: false

💡 Note: Player 1 takes 2, Player 2 takes 5, Player 1 takes 1. Player 1 gets 3, Player 2 gets 5. Player 2 wins.

Example 2 — Player 1 Wins Optimally

$ Input: nums = [1,5,233,7]

› Output: true

💡 Note: Player 1 takes 1, Player 2 takes 7, Player 1 takes 233, Player 2 takes 5. Player 1 gets 234, Player 2 gets 12. Player 1 wins.

Example 3 — Equal Scores

$ Input: nums = [1,1]

› Output: true

💡 Note: Player 1 takes any element and gets 1, Player 2 gets 1. Tie goes to Player 1.

Constraints

1 ≤ nums.length ≤ 20
-10⁷ ≤ nums[i] ≤ 10⁷

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,5,233,7] with players taking turns

Optimal Play

Each player chooses to maximize their advantage

Winner

Player 1 wins if they can get ≥ 50% of total

Key Takeaway

🎯 Key Insight: Track score differences instead of absolute scores to determine optimal play

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is to track the maximum score difference (advantage) a player can achieve rather than absolute scores. The optimal approach uses dynamic programming to compute this difference for all subarrays. Time: O(n²), Space: O(n) with space optimization.

Common Approaches

Approach	Time	Space	Notes
✓ Memoized Recursion	O(n²)	O(n²)	Cache recursive results to avoid redundant calculations
Brute Force Recursion	O(2ⁿ)	O(n)	Recursively explore all possible moves for both players
2D Dynamic Programming	O(n²)	O(n²)	Bottom-up DP table storing score differences for all subarrays
Space-Optimized DP	O(n²)	O(n)	1D DP array using only current and previous rows

Memoized Recursion — Algorithm Steps

Use recursion with memoization table
Cache results for each (left, right) subarray
Return cached result if already computed
Compute and store new results

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_N 1000
int memo[MAX_N][MAX_N];
bool memoized[MAX_N][MAX_N];

int gameScoreDiff(int* nums, int left, int right) {
    if (left > right) return 0;
    
    if (memoized[left][right]) {
        return memo[left][right];
    }
    
    int takeLeft = nums[left] - gameScoreDiff(nums, left + 1, right);
    int takeRight = nums[right] - gameScoreDiff(nums, left, right - 1);
    
    memo[left][right] = takeLeft > takeRight ? takeLeft : takeRight;
    memoized[left][right] = true;
    return memo[left][right];
}

bool solution(int* nums, int n) {
    memset(memoized, false, sizeof(memoized));
    return gameScoreDiff(nums, 0, n - 1) >= 0;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    bool result = solution(nums, n);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Each of the n² possible subarrays is computed once

⚠ Quadratic Growth

Space Complexity

O(n²)

Memoization table stores results for all subarray combinations plus recursion stack

⚠ Quadratic Space

78.0K Views

Medium Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen