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:
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.
Examples
Example 1
Input: points = [2,4], m = 3
Output: 4
Explanation:
Initially, index i = -1 and gameScore = [0, 0] .
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] .
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
3449. Maximize the Minimum Game Score
Hard
50 Points
Array
Binary Search
Greedy
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:
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.
Examples
Example 1
Input: points = [2,4], m = 3
Output: 4
Explanation:
Initially, index i = -1 and gameScore = [0, 0] .
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] .
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
Maximize the Minimum Game Score - Practice Coding | SlaveCode