3449. Maximize the Minimum Game Score LeetCode Solution

In this guide, you will get 3449. Maximize the Minimum Game Score LeetCode Solution with the best time and space complexity. The solution to Maximize the Minimum Game Score problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Maximize the Minimum Game Score solution in C++
4. Maximize the Minimum Game Score solution in Java
5. Maximize the Minimum Game Score solution in Python
6. Additional Resources

Problem Statement of Maximize the Minimum Game Score

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

Complexity Analysis

• Time Complexity: \log\left(\frac{m + 1}{2} \cdot \texttt{points[0]}\right)
• Space Complexity: O(1)

3449. Maximize the Minimum Game Score LeetCode Solution in C++

class Solution {
 public:
  long long maxScore(vector<int>& points, int m) {
    long l = 0;
    long r = (m + 1L) / 2 * points[0] + 1;

    while (l < r) {
      const long mid = (l + r + 1) / 2;
      if (isPossible(points, mid, m))
        l = mid;
      else
        r = mid - 1;
    }

    return l;
  }

 private:
  // Returns true if it is possible to achieve the maximum minimum value `x`
  // with `m` number of moves.
  bool isPossible(const vector<int>& points, long minVal, long m) {
    long moves = 0;
    long prevMoves = 0;  // to track remaining moves from the previous point
    for (int i = 0; i < points.size(); ++i) {
      // ceil(minVal / point)
      const long required =
          max(0L, (minVal + points[i] - 1) / points[i] - prevMoves);
      if (required > 0) {
        moves += 2L * required - 1;
        prevMoves = required - 1;
      } else if (i + 1 < points.size()) {
        moves += 1;
        prevMoves = 0;
      }
      if (moves > m)
        return false;
    }
    return true;
  };
};
/* code provided by PROGIEZ */

3449. Maximize the Minimum Game Score LeetCode Solution in Java

class Solution {
  public long maxScore(int[] points, int m) {
    long l = 0;
    long r = ((long) m + 1) / 2 * points[0] + 1;

    while (l < r) {
      final long mid = (l + r + 1) / 2;
      if (isPossible(points, mid, m))
        l = mid;
      else
        r = mid - 1;
    }

    return l;
  }

  // Returns true if it is possible to achieve the maximum minimum value `x`
  // with `m` number of moves.
  private boolean isPossible(int[] points, long minVal, long m) {
    long moves = 0;
    long prevMoves = 0; // to track remaining moves from the previous point
    for (int i = 0; i < points.length; ++i) {
      // ceil(minVal / point)
      final long required = Math.max(0, (minVal + points[i] - 1) / points[i] - prevMoves);
      if (required > 0) {
        moves += 2L * required - 1;
        prevMoves = required - 1;
      } else if (i + 1 < points.length) {
        moves += 1;
        prevMoves = 0;
      }
      if (moves > m)
        return false;
    }
    return true;
  }
}
// code provided by PROGIEZ

3449. Maximize the Minimum Game Score LeetCode Solution in Python

class Solution:
  def maxScore(self, points: list[int], m: int) -> int:
    def isPossible(minVal: int, m: int) -> bool:
      """
      Returns True if it is possible to achieve the maximum minimum value `x`
      with `m` number of moves.
      """
      moves = 0
      prevMoves = 0  # to track remaining moves from the previous point
      for i, point in enumerate(points):
        required = (minVal + point - 1) // point  # ceil(minVal / point)
        required = max(0, required - prevMoves)
        if required > 0:
          moves += 2 * required - 1
          prevMoves = required - 1
        elif i + 1 < len(points):
          moves += 1
          prevMoves = 0
        if moves > m:
          return False
      return True

    l = 0
    r = (m + 1) // 2 * points[0] + 1

    while l < r:
      mid = (l + r + 1) // 2
      if isPossible(mid, m):
        l = mid
      else:
        r = mid - 1

    return l
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.