Maximize the Minimum Game Score - Practice Coding Problems

Maximize the Minimum Game Score - Problem

You are given an array points of size n and an integer m. There is another array gameScore of size n, where gameScore[i] represents the score achieved at the i-th game. Initially, gameScore[i] == 0 for all i.

You start at index -1, which is outside the array (before the first position at index 0). You can make at most m moves. In each move, you can either:

Increase the index by 1 and add points[i] to gameScore[i]
Decrease the index by 1 and add points[i] to gameScore[i]

Note that the index must always remain within the bounds of the array after the first move.

Return the maximum possible minimum value in gameScore after at most m moves.

Input & Output

Example 1 — Basic Expansion

$ Input: points = [3,1,4,2], m = 4

› Output: 2

💡 Note: Start at position 0, then visit positions 1 and 2. With 4 moves, we can achieve scores [3,2,4,0], giving minimum = 2.

Example 2 — Limited Moves

$ Input: points = [1,5,2,3], m = 3

› Output: 1

💡 Note: With only 3 moves, we can visit positions 0,1,2 getting scores [1,5,2,0]. Minimum among visited is 1.

Example 3 — Single Element

$ Input: points = [10], m = 2

› Output: 20

💡 Note: Only one position exists. Use both moves on position 0: score[0] = 20, minimum = 20.

Constraints

1 ≤ points.length ≤ 10⁵
1 ≤ points[i] ≤ 10⁴
1 ≤ m ≤ 2 × 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Points array [3,1,4,2] with m=4 moves

Process

Start at index -1, make strategic moves to maximize minimum score

Output

Maximum possible minimum score = 2

Key Takeaway

🎯 Key Insight: Binary search the answer space and verify feasibility with greedy expansion

Asked in

G Google 35 f Meta 28 a Amazon 25 M Microsoft 20

The key insight is to use binary search on the answer space combined with greedy verification. We binary search the maximum achievable minimum score and for each candidate, greedily check if it's achievable within m moves. Best approach is Binary Search + Greedy. Time: O(log(sum) × n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search on Answer	O(log(sum) × n)	O(1)	Binary search the maximum achievable minimum score
Greedy Expansion	O(m)	O(n)	Greedily expand from starting position to maximize minimum score
Brute Force Simulation	O(2^m × n)	O(m)	Try all possible sequences of moves to find maximum minimum score

Binary Search on Answer — Algorithm Steps

Binary search on possible minimum scores
For each candidate, greedily check if achievable
Use two pointers to optimally distribute moves
Return the maximum feasible minimum score

Visualization

Tap to expand

Step-by-Step Walkthrough

Search Space

Binary search between 0 and sum of all points

Greedy Check

For each candidate, verify if achievable with m moves

Optimal Answer

Find maximum feasible minimum score

Code -

solution.c — C

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

int findMin(int* arr, int n) {
    int min = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] < min) min = arr[i];
    }
    return min;
}

bool canAchieve(int* points, int n, int m, int target) {
    int* scores = (int*)calloc(n, sizeof(int));
    int moves = 0;
    int left = 0, right = 0;
    
    scores[0] += points[0];
    moves++;
    
    while (moves < m) {
        bool needLeft = left > 0 && scores[left-1] < target;
        bool needRight = right < n-1 && scores[right+1] < target;
        
        if (!needLeft && !needRight) break;
        
        if (needLeft && (!needRight || left == right)) {
            left--;
            scores[left] += points[left];
        } else if (needRight) {
            right++;
            scores[right] += points[right];
        } else {
            break;
        }
        
        moves++;
    }
    
    bool result = findMin(scores, n) >= target;
    free(scores);
    return result;
}

int solution(int* points, int n, int m) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += points[i];
    }
    
    int left = 0, right = sum;
    int result = 0;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (canAchieve(points, n, m, mid)) {
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int points[100];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        points[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int m;
    scanf("%d", &m);
    
    int result = solution(points, n, m);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(log(sum) × n)

Binary search on answer space (log of sum of points) times O(n) greedy check

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

28.5K Views

Medium Frequency

~35 min Avg. Time

890 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search on Answer — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler