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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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 * 10^4
  • 1 <= points[i] <= 10^6
  • 1 <= m <= 10^9

Examples

Solution

Method 1 – Binary Search with Greedy Allocation

Intuition

To maximize the minimum value in gameScore, we can use binary search on the answer. For each candidate minimum, we check if it’s possible to distribute at most m moves so that every gameScore[i] is at least that value, by greedily allocating moves to the most efficient positions.

Approach

  1. Use binary search for the answer between 0 and the maximum possible sum of moves at any index.
  2. For each mid value, check if it’s possible to achieve at least mid at every index with at most m moves:
    • For each index, calculate the minimum number of moves needed to reach mid at that index: ceil((mid) / points[i]).
    • Sum the moves for all indices.
    • If the total moves needed is less than or equal to m, it’s possible.
  3. If possible, try a higher value; otherwise, try lower.
  4. Return the largest value for which it is possible.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int maximizeMinScore(vector<int>& points, int m) {
        int n = points.size();
        int l = 0, r = 1e15, ans = 0;
        while (l <= r) {
            long long mid = l + (r - l) / 2, need = 0;
            for (int i = 0; i < n; ++i) {
                need += (mid + points[i] - 1) / points[i];
            }
            if (need <= m) { ans = mid; l = mid + 1; }
            else r = mid - 1;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func maximizeMinScore(points []int, m int) int {
    n := len(points)
    l, r, ans := 0, int(1e15), 0
    for l <= r {
        mid := (l + r) / 2
        need := 0
        for i := 0; i < n; i++ {
            need += (mid + points[i] - 1) / points[i]
        }
        if need <= m {
            ans = mid
            l = mid + 1
        } else {
            r = mid - 1
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int maximizeMinScore(int[] points, int m) {
        int n = points.length;
        long l = 0, r = (long)1e15, ans = 0;
        while (l <= r) {
            long mid = (l + r) / 2, need = 0;
            for (int i = 0; i < n; i++) {
                need += (mid + points[i] - 1) / points[i];
            }
            if (need <= m) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return (int)ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    fun maximizeMinScore(points: IntArray, m: Int): Int {
        var l = 0L
        var r = 1_000_000_000_000_000L
        var ans = 0L
        while (l <= r) {
            val mid = (l + r) / 2
            var need = 0L
            for (p in points) {
                need += (mid + p - 1) / p
            }
            if (need <= m) {
                ans = mid
                l = mid + 1
            } else {
                r = mid - 1
            }
        }
        return ans.toInt()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def maximizeMinScore(self, points: list[int], m: int) -> int:
        def enough(x: int) -> bool:
            return sum((x + p - 1) // p for p in points) <= m
        l, r, ans = 0, 10**15, 0
        while l <= r:
            mid = (l + r) // 2
            if enough(mid):
                ans = mid
                l = mid + 1
            else:
                r = mid - 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn maximize_min_score(points: Vec<i64>, m: i64) -> i64 {
        let (mut l, mut r, mut ans) = (0, 1_000_000_000_000_000, 0);
        while l <= r {
            let mid = (l + r) / 2;
            let need: i64 = points.iter().map(|&p| (mid + p - 1) / p).sum();
            if need <= m {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    maximizeMinScore(points: number[], m: number): number {
        let l = 0, r = 1e15, ans = 0;
        while (l <= r) {
            const mid = Math.floor((l + r) / 2);
            let need = 0;
            for (const p of points) {
                need += Math.floor((mid + p - 1) / p);
            }
            if (need <= m) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log X) — where n is the number of points and X is the search range (up to 1e15).
  • 🧺 Space complexity: O(1) — only a few variables are used.