Skip to main content
Talentd

Maximize the Minimum Game Score - Solution & Explanation

HardArrayBinary SearchGreedy4 min readAsked at: Amazon, Infosys
Practice this problem

Problem Statement

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 ith 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.

 

Example 1:

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

Output: 4

Explanation:

Initially, index i = -1 and gameScore = [0, 0].

Move Index gameScore
Increase i 0 [2, 0]
Increase i 1 [2, 4]
Decrease i 0 [4, 4]

The minimum value in gameScore is 4, and this is the maximum possible minimum among all configurations. Hence, 4 is the output.

Example 2:

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

Output: 2

Explanation:

Initially, index i = -1 and gameScore = [0, 0, 0].

Move Index gameScore
Increase i 0 [1, 0, 0]
Increase i 1 [1, 2, 0]
Decrease i 0 [2, 2, 0]
Increase i 1 [2, 4, 0]
Increase i 2 [2, 4, 3]

The minimum value in gameScore is 2, and this is the maximum possible minimum among all configurations. Hence, 2 is the output.

 

Constraints:

  • 2 <= n == points.length <= 5 * 104
  • 1 <= points[i] <= 106
  • 1 <= m <= 109

Approach Overview

Problem Overview: You are given an array where each position contributes a certain number of points every time it is visited. With a limited number of moves, you want to distribute visits across indices so that the minimum score among all positions becomes as large as possible.

Approach 1: Brute Force Simulation (O(n * m) time, O(1) space)

A straightforward idea is to simulate moves and try to balance visits across indices so every position accumulates points. For each step, you decide where to move next and track how many times each index has been visited. After all moves are used, compute the minimum score across the array. This approach quickly becomes infeasible because the number of possible movement patterns grows rapidly with the number of moves. It works only for very small inputs and mainly helps build intuition about how visit counts translate into score.

Approach 2: Binary Search + Greedy Feasibility Check (O(n log answer) time, O(1) space)

The key observation: instead of directly constructing the optimal sequence of moves, you can ask a simpler question — can we achieve a minimum score of X for every index?. If a target score X is achievable, then any value smaller than X is also achievable. This monotonic property makes the problem a perfect candidate for binary search.

For a candidate score X, compute how many visits each index must receive. If an index gives points[i] per visit, then it needs at least ceil(X / points[i]) visits to reach the target score. A greedy pass determines whether these required visits can be scheduled within the total move budget while respecting movement constraints between adjacent positions. The simulation aggregates required visits and tracks the number of moves needed to bounce between positions efficiently.

If the greedy check fits within the allowed moves, the score X is feasible and you try a larger value. Otherwise, reduce the search space. This pattern is common in optimization problems combining greedy reasoning with binary search.

Recommended for interviews: Interviewers expect the binary search + greedy approach. Brute force shows you understand how scores accumulate from visits, but the optimal solution demonstrates the ability to recognize monotonic search space and design a feasibility check that runs in linear time.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force SimulationO(n * m)O(1)Useful only for understanding the mechanics of visit counts and score accumulation.
Binary Search + Greedy FeasibilityO(n log answer)O(1)Best general solution. Works well when the objective (minimum score) has monotonic feasibility.

Video Solution

Maximize the Minimum Game Score | Super Detailed | Dry Runs | Leetcode 3449 | codestorywithMIK • codestorywithMIK • 4,253 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Maximize the Minimum Game Score easy or hard?
Maximize the Minimum Game Score is classified as Hard. The difficulty comes from recognizing the monotonic property that allows binary search and designing a correct greedy feasibility check to validate whether a target score can be achieved.
Maximize the Minimum Game Score Python/Java solution
Implement binary search on the target minimum score. For each candidate value, run a helper function that calculates required visits per index and verifies the move limit using a greedy pass. The same logic works across Python, Java, C++, and Go with O(n log answer) complexity.
How to solve Maximize the Minimum Game Score in O(n log n)?
Use binary search on the minimum achievable score and run a greedy feasibility check for each candidate value. For a target score X, compute the number of visits required at each index using ceil(X / points[i]). If the total movement needed to achieve these visits fits within the allowed moves, the score is feasible.
What is the best approach for Maximize the Minimum Game Score?
Binary search combined with a greedy feasibility check is the most efficient approach. You binary search the target minimum score and verify if it can be achieved within the move limit. The feasibility step calculates required visits per index and ensures the move count stays within bounds, giving an overall time complexity of O(n log answer).
Is Maximize the Minimum Game Score asked at Google/Amazon/Meta?
Problems combining binary search with greedy feasibility checks frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that maximize a minimum value under constraints are especially common in system optimization and allocation-style questions.
What data structure is used in Maximize the Minimum Game Score?
The solution primarily uses arrays and simple counters. The main techniques are binary search over the answer space and greedy calculations to determine the number of visits required per index.
What is the time complexity of Maximize the Minimum Game Score?
The optimal solution runs in O(n log answer) time and O(1) space. Binary search explores possible minimum score values, and each feasibility check scans the array once to compute required visits and validate the move budget.

Ready to solve this problem?

Practice Maximize the Minimum Game Score with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays