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:
points[i] to gameScore[i].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 * 1041 <= points[i] <= 1061 <= m <= 109Problem 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| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n * m) | O(1) | Useful only for understanding the mechanics of visit counts and score accumulation. |
| Binary Search + Greedy Feasibility | O(n log answer) | O(1) | Best general solution. Works well when the objective (minimum score) has monotonic feasibility. |
Maximize the Minimum Game Score | Super Detailed | Dry Runs | Leetcode 3449 | codestorywithMIK • codestorywithMIK • 3,831 views views
Watch 3 more video solutions →Practice Maximize the Minimum Game Score with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor