LeetCode 3449 - Maximize the Minimum Game Score

LeetCode Problem 3449

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Greedy

Solution

Problem Understanding

You are given an array points, where points[i] is the amount added to gameScore[i] every time you land on index i.

The player starts outside the array at position -1. Each move changes the current position by exactly one:

• Moving right from i to i + 1
• Moving left from i to i - 1

Whenever you land on an index, that index immediately gains its corresponding score value.

The goal is not to maximize the total score. Instead, after making at most m moves, we look at the smallest value inside gameScore, and we want that minimum value to be as large as possible.

In other words, if the final score array is:

gameScore = [12, 20, 15, 18]

then the value that matters is:

min(gameScore) = 12

and we want to maximize that minimum.

The constraints are large:

• n can be up to 5 * 10^4
• m can be up to 10^9
• points[i] can be up to 10^6

These limits immediately rule out any simulation of all possible paths. The number of moves alone can be one billion, so we need a mathematical characterization of what is achievable.

Several edge cases are important:

• Very small move budgets where some indices may barely be reachable.
• Arrays where one points[i] is much smaller than the others, since that index becomes the bottleneck.
• Extremely large values of m, where the answer can become very large and requires 64-bit arithmetic.
• Situations where revisiting indices is necessary, because a single visit is not enough to reach the target minimum score.

Approaches

Brute Force

A brute force approach would attempt to explore possible movement sequences and track the resulting gameScore array.

For every move, the player may move left or right, creating an exponential number of possible paths. Even with aggressive pruning, the search space becomes enormous.

The approach is conceptually correct because it examines every possible valid movement sequence and therefore eventually finds the optimal answer. However, it is completely infeasible for the given constraints.

Key Insight

The crucial observation is that the answer is monotonic.

Suppose we ask:

Can we make every gameScore[i] at least X within m moves?

If the answer is yes for some value X, then it is also yes for every value smaller than X.

If the answer is no for some value X, then it is also no for every value larger than X.

This monotonic property allows binary search on the answer.

The remaining challenge is designing a fast feasibility check.

For a target minimum score X, index i must be visited at least:

ceil(X / points[i])

times.

The movement structure is very restrictive because movement occurs only between adjacent positions. A greedy left-to-right process can determine the minimum number of moves needed to satisfy all required visit counts.

The key optimization is recognizing that when we repeatedly move back and forth between adjacent indices, visits generated for one index also help its neighbor. We can carry this information forward while processing the array.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Explores movement sequences directly
Optimal	O(n log M)	O(1)	Binary search on answer with greedy feasibility check

Here, M represents the maximum possible answer value.

Algorithm Walkthrough

Binary Search Framework

We binary search the largest achievable minimum score.

For a candidate value target, we check whether every index can reach at least target.

Feasibility Check

For index i, we need:

requiredVisits = ceil(target / points[i])

If an index has already received some visits from previous back-and-forth movements, we can subtract those visits from what is still needed.

Step-by-Step Process

1. Initialize moves = 0.
2. Maintain a variable called prevMoves.

This represents how many extra visits the current position already receives because of the bouncing performed while satisfying the previous index. 3. Process indices from left to right. 4. For index i, compute:

required = ceil(target / points[i])

5. Some of these visits may already be covered by prevMoves.

Therefore:

required = max(0, required - prevMoves)

6. If required > 0, we must generate additional visits.

Each additional visit requirement can be satisfied by moving back and forth between adjacent indices.

The minimum move cost becomes:

2 * required - 1

because the first arrival costs one move and every additional visit requires a round trip. 7. Add that cost to moves. 8. Set:

prevMoves = required - 1

since these back-and-forth movements also create visits for the next index. 9. If required == 0, then this index is already satisfied.

If it is not the last index, we still need one move to advance to the next position:

moves += 1

10. If at any point moves > m, the target score is impossible.
11. If all indices are processed within m moves, the target score is achievable.

Why it works

The greedy check always uses the minimum number of moves necessary to satisfy each position before advancing. Any extra bouncing beyond what is required would only increase the move count and cannot help produce a better feasibility result.

The variable prevMoves correctly captures the overlap created by back-and-forth movements. Visits generated while satisfying one index partially satisfy the next index as well. Because the array is processed from left to right and movement is restricted to adjacent positions, this greedy accounting yields the minimum move count required for a given target score.

Python Solution

from typing import List

class Solution:
    def maxScore(self, points: List[int], m: int) -> int:
        def can_achieve(target: int) -> bool:
            moves = 0
            prev_moves = 0

            for i, point in enumerate(points):
                required = (target + point - 1) // point
                required = max(0, required - prev_moves)

                if required > 0:
                    moves += 2 * required - 1
                    prev_moves = required - 1
                elif i + 1 < len(points):
                    moves += 1
                    prev_moves = 0

                if moves > m:
                    return False

            return True

        left = 0
        right = ((m + 1) // 2) * points[0] + 1

        while left < right:
            mid = (left + right + 1) // 2

            if can_achieve(mid):
                left = mid
            else:
                right = mid - 1

        return left

The solution consists of two parts.

The outer binary search finds the maximum achievable minimum score. Because feasibility is monotonic, we can safely discard half of the search space after every check.

The helper function can_achieve computes the minimum moves needed for a candidate score. For each index, it determines how many visits are required and subtracts any visits already contributed by previous bouncing operations. If additional visits are needed, it adds the corresponding move cost and updates prev_moves so the next index can reuse those visits.

The binary search continues until the largest feasible value is found.

Go Solution

func maxScore(points []int, m int) int64 {
	canAchieve := func(target int64) bool {
		var moves int64 = 0
		var prevMoves int64 = 0

		for i, point := range points {
			required := (target + int64(point) - 1) / int64(point)

			if required > prevMoves {
				required -= prevMoves
			} else {
				required = 0
			}

			if required > 0 {
				moves += 2*required - 1
				prevMoves = required - 1
			} else if i+1 < len(points) {
				moves++
				prevMoves = 0
			}

			if moves > int64(m) {
				return false
			}
		}

		return true
	}

	var left int64 = 0
	var right int64 = int64((m+1)/2)*int64(points[0]) + 1

	for left < right {
		mid := (left + right + 1) / 2

		if canAchieve(mid) {
			left = mid
		} else {
			right = mid - 1
		}
	}

	return left
}

The Go implementation follows exactly the same logic as the Python version.

The most important Go-specific detail is using int64 throughout the binary search and feasibility computation. Since m can be as large as 10^9 and scores can grow into the trillions, ordinary 32-bit integers would overflow.

Worked Examples

Example 1

points = [2, 4]
m = 3

Suppose binary search checks:

target = 4

Required visits:

Index	Points	Required Visits
0	2	2
1	4	1

Feasibility check:

Step	Index	Required After Reuse	Moves Added	Total Moves	prevMoves
1	0	2	3	3	1
2	1	0	0	3	1

Total moves:

3 <= m

So score 4 is achievable.

Trying a larger value fails, therefore the answer is:

4

Example 2

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

Check:

target = 2

Required visits:

Index	Points	Required Visits
0	1	2
1	2	1
2	3	1

Feasibility process:

Step	Index	Required After Reuse	Moves Added	Total Moves	prevMoves
1	0	2	3	3	1
2	1	0	1	4	0
3	2	1	1	5	0

Total:

5 <= m

So target 2 is feasible.

Trying target 3 exceeds the move budget, therefore:

answer = 2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log M)	Binary search performs O(log M) checks, each check scans the array once
Space	O(1)	Only a few variables are maintained

The feasibility check is linear in the number of indices. The binary search range is proportional to the maximum possible answer, giving a logarithmic number of iterations. Since no auxiliary arrays or data structures are required, the space usage remains constant.

Test Cases

sol = Solution()

assert sol.maxScore([2, 4], 3) == 4      # provided example 1
assert sol.maxScore([1, 2, 3], 5) == 2   # provided example 2

assert sol.maxScore([1, 1], 1) == 0      # cannot visit both indices
assert sol.maxScore([1, 1], 2) == 1      # exactly one visit each

assert sol.maxScore([5, 5], 3) == 5      # symmetric values
assert sol.maxScore([10, 1], 3) == 1     # bottleneck second index

assert sol.maxScore([1, 1000000], 3) == 1  # huge value disparity
assert sol.maxScore([1000000, 1000000], 3) == 1000000  # large scores

assert sol.maxScore([3, 3, 3], 5) == 3   # one visit each, extra bounce
assert sol.maxScore([2, 2, 2], 7) == 4   # multiple revisits required

assert sol.maxScore([1, 1, 1, 1], 7) == 1  # enough to reach all indices
assert sol.maxScore([1, 1, 1, 1], 8) == 2  # larger minimum becomes possible

assert sol.maxScore([7, 4, 9, 2], 1000000000) > 0  # stress test

Test Summary

Test	Why
[2,4], 3	Official example
[1,2,3], 5	Official example
[1,1], 1	Not enough moves to reach all positions
[1,1], 2	Smallest feasible full coverage
[5,5], 3	Symmetric array
[10,1], 3	Bottleneck index determines answer
[1,1000000], 3	Extreme value imbalance
[1000000,1000000], 3	Large score values
[3,3,3], 5	Limited revisits
[2,2,2], 7	Multiple required visits
[1,1,1,1], 7	Barely enough traversal
Large m case	Verifies 64-bit handling

Edge Cases

Very Small Move Budget

Consider:

points = [1, 1]
m = 1

After one move, the player can only reach index 0. Index 1 remains at score 0, so the minimum score is 0.

A common bug is assuming every index can always receive at least one visit. The feasibility check naturally rejects any target requiring visits to unreachable indices because the move count exceeds the budget.

One Extremely Small Point Value

Consider:

points = [1000, 1, 1000]

The middle index becomes the bottleneck. To increase the minimum score, that index must be visited many more times than its neighbors.

A naive implementation might focus on total score accumulation, but the correct solution computes required visits independently for each index and therefore handles bottlenecks correctly.

Large Values Causing Overflow

Consider:

points = [1000000, 1000000]
m = 1000000000

The answer can be extremely large.

Using 32-bit integers may overflow during binary search bounds or move calculations. Both implementations use 64-bit arithmetic for all score-related computations, ensuring correctness even at the upper limits of the constraints.

The binary search plus greedy feasibility check is the key insight that makes this hard problem tractable, reducing an enormous search space into an efficient O(n log M) solution.