LeetCode Problem 3207

Difficulty: 🟡 Medium
Topics: Array, Greedy

Solution

LeetCode 3207 - Maximum Points After Enemy Battles

Problem Understanding

The problem gives us a list of enemies, where each enemy has an associated energy value. We also start with some initial amount of energy called currentEnergy.

We begin with zero points, and every enemy starts as unmarked.

We are allowed to repeatedly perform one of two operations:

1. We can fight an unmarked enemy if we currently have enough energy to pay its energy cost. Doing this gives us one point, and our energy decreases by that enemy's energy value.
2. If we already have at least one point, we may instead mark an unmarked enemy. Marking an enemy increases our energy by that enemy's energy value, but does not increase points.

The important detail is that the first operation does not mark the enemy. That means the same enemy can potentially be used repeatedly for gaining points. However, the second operation permanently marks an enemy, meaning it can no longer participate in future operations.

The goal is to maximize the total number of points obtained.

The constraints are large, up to 10^5 enemies and energy values up to 10^9. This immediately tells us that exponential search or state simulation is impossible. We need an efficient greedy observation.

A few edge cases are especially important:

• If our initial energy is smaller than every enemy energy, we cannot even perform the first operation once. Since the second operation requires at least one point, the answer is zero.
• If there is only one enemy, we may repeatedly fight that enemy until energy runs out.
• Large energy values require careful handling in Go, because the answer can exceed 32 bit integer limits.
• The first operation can reuse the same enemy indefinitely, which is the key observation that changes the problem dramatically.

Approaches

Brute Force Approach

A brute force solution would attempt to simulate all possible sequences of operations.

At every step, we could:

• Fight any currently affordable unmarked enemy
• Mark any unmarked enemy if we have at least one point

This creates a huge branching factor. Since enemies can be fought repeatedly before being marked, the number of possible states becomes enormous.

A state would need to track:

• Current energy
• Current points
• Which enemies are marked

This essentially becomes an exponential state space exploration problem.

Although such an approach would eventually find the optimal answer, it is completely infeasible for 10^5 enemies.

Key Insight

The crucial observation is that the first operation does not mark the enemy.

That means if we want to gain points as efficiently as possible, we should repeatedly fight the enemy with the smallest energy cost. Every point gained from that enemy costs the least possible amount of energy.

Suppose the minimum enemy energy is minEnergy.

Then every minEnergy units of energy can always be converted into one point by repeatedly fighting that enemy.

Now consider the second operation. Marking an enemy simply transfers its energy into our energy pool, at the cost of requiring at least one existing point.

Since eventually all enemy energies can be absorbed into our energy reserve, the total usable energy becomes:

currentEnergy + sum(enemyEnergies except the minimum one used repeatedly)

In fact, once we can initially afford the minimum enemy even once, all remaining enemy energies can eventually be converted into additional usable energy.

Therefore:

• If currentEnergy < minEnergy, answer is 0
• Otherwise, total usable energy becomes:

currentEnergy + sum(enemyEnergies) - minEnergy

Since every point costs minEnergy, the maximum number of points is:

(currentEnergy + sum(enemyEnergies) - minEnergy) // minEnergy

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Explores all operation sequences
Optimal	O(n)	O(1)	Uses greedy observation with minimum energy enemy

Algorithm Walkthrough

1. Traverse the array once to compute:

• The minimum enemy energy
• The total sum of all enemy energies

2. Check whether the initial energy is smaller than the minimum enemy energy.

• If yes, we cannot perform even a single fight.
• Since marking requires at least one point, no operations are possible.
• Return 0.

3. Otherwise, reserve the smallest enemy as the reusable enemy for repeatedly gaining points.

• We never want to mark this enemy because it gives the cheapest possible point conversion.

4. All other enemies can eventually be marked to transfer their energies into our energy pool.

• Total usable energy becomes:

currentEnergy + totalSum - minEnergy

1. Since each point costs exactly minEnergy, divide the total usable energy by minEnergy.
2. Return the result.

Why it works

The algorithm works because the cheapest enemy dominates all other choices for gaining points. Any point earned using a larger energy enemy is strictly less efficient.

Therefore, the optimal strategy always repeatedly fights the minimum energy enemy and uses all other enemies only as energy sources through marking. This converts the entire problem into a simple energy accounting formula.

Python Solution

from typing import List

class Solution:
    def maximumPoints(self, enemyEnergies: List[int], currentEnergy: int) -> int:
        minimum_energy = min(enemyEnergies)

        if currentEnergy < minimum_energy:
            return 0

        total_energy = sum(enemyEnergies)

        usable_energy = currentEnergy + total_energy - minimum_energy

        return usable_energy // minimum_energy

The implementation is intentionally compact because the mathematical observation completely removes the need for simulation.

First, we compute the smallest enemy energy because that enemy will always be the optimal choice for repeatedly earning points.

Next, we check whether the initial energy is sufficient to defeat that enemy even once. If not, the answer must be zero because no operations are possible.

We then compute the total energy available across all enemies. Since every enemy except the minimum one can eventually be marked and converted into energy, we add their energies into the usable energy pool.

Finally, dividing by the minimum energy gives the maximum number of points obtainable.

Go Solution

package main

func minimum(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func maximumPoints(enemyEnergies []int, currentEnergy int) int64 {
	minEnergy := enemyEnergies[0]
	totalEnergy := int64(0)

	for _, energy := range enemyEnergies {
		minEnergy = minimum(minEnergy, energy)
		totalEnergy += int64(energy)
	}

	if currentEnergy < minEnergy {
		return 0
	}

	usableEnergy := int64(currentEnergy) + totalEnergy - int64(minEnergy)

	return usableEnergy / int64(minEnergy)
}

The Go solution follows the exact same logic as the Python version.

The main implementation detail is integer handling. Since energy values and array sizes can both be large, the total accumulated energy may exceed 32 bit integer limits. Therefore, int64 is used for all accumulated values and for the final answer.

Go slices are naturally dynamic arrays, so no special handling for empty arrays is necessary because the constraints guarantee at least one enemy.

Worked Examples

Example 1

enemyEnergies = [3, 2, 2]
currentEnergy = 2

First compute:

Variable	Value
minimum_energy	2
total_energy	7

Since currentEnergy >= minimum_energy, we can proceed.

Now compute usable energy:

usable_energy = 2 + 7 - 2 = 7

Maximum points:

7 // 2 = 3

Answer:

3

A valid sequence is:

Step	Action	Energy	Points
Start	Initial state	2	0
1	Fight enemy with energy 2	0	1
2	Mark enemy with energy 3	3	1
3	Fight enemy with energy 2	1	2
4	Mark enemy with energy 2	3	2
5	Fight enemy with energy 2	1	3

Example 2

enemyEnergies = [2]
currentEnergy = 10

Compute:

Variable	Value
minimum_energy	2
total_energy	2

Usable energy:

10 + 2 - 2 = 10

Maximum points:

10 // 2 = 5

Answer:

5

We simply fight the same enemy repeatedly five times.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single traversal for min and sum
Space	O(1)	Only constant extra variables used

The algorithm only scans the input array once. No sorting, recursion, or auxiliary data structures are required. This makes the solution optimal for the given constraints.

Test Cases

from typing import List

class Solution:
    def maximumPoints(self, enemyEnergies: List[int], currentEnergy: int) -> int:
        minimum_energy = min(enemyEnergies)

        if currentEnergy < minimum_energy:
            return 0

        total_energy = sum(enemyEnergies)

        usable_energy = currentEnergy + total_energy - minimum_energy

        return usable_energy // minimum_energy

solution = Solution()

assert solution.maximumPoints([3, 2, 2], 2) == 3  # Provided example 1

assert solution.maximumPoints([2], 10) == 5  # Provided example 2

assert solution.maximumPoints([5], 4) == 0  # Cannot fight even once

assert solution.maximumPoints([1], 0) == 0  # Zero initial energy

assert solution.maximumPoints([1], 1) == 1  # Exactly enough for one fight

assert solution.maximumPoints([1, 1, 1], 1) == 3  # All minimum values

assert solution.maximumPoints([10, 20, 30], 10) == 6  # Use larger enemies as energy

assert solution.maximumPoints([2, 1000000000], 2) == 500000001  # Large values

assert solution.maximumPoints([4, 6, 8], 3) == 0  # Initial energy too small

assert solution.maximumPoints([5, 5, 5, 5], 20) == 7  # Repeated reuse of same enemy

Test	Why
[3,2,2], 2	Validates provided example
[2], 10	Single enemy repeated many times
[5], 4	Cannot start any operation
[1], 0	Zero initial energy
[1], 1	Exact affordability boundary
[1,1,1], 1	Multiple identical minimum enemies
[10,20,30], 10	Large energy accumulation through marking
[2,1000000000], 2	Very large integer handling
[4,6,8], 3	Initial energy below minimum
[5,5,5,5], 20	Repeated point farming

Edge Cases

One important edge case occurs when the initial energy is smaller than the minimum enemy energy. In this situation, we cannot perform the first operation even once. Since the second operation requires already having at least one point, the process cannot begin at all. The implementation handles this immediately with an early return of 0.

Another important case is when there is only one enemy. A naive implementation might incorrectly assume enemies become unavailable after fighting them once. However, the first operation does not mark the enemy. The implementation correctly recognizes that the same enemy may be reused indefinitely until energy runs out.

Large integer values are also a significant edge case. Energy values can be as large as 10^9, and there may be 10^5 enemies. The total sum can therefore exceed 32 bit integer capacity. The Go implementation explicitly uses int64 for accumulation and division to avoid overflow bugs.

A final subtle case occurs when multiple enemies share the same minimum energy value. The algorithm still works correctly because only one minimum energy enemy needs to remain unmarked for repeated point generation. The others can safely be marked later to recover additional energy.