# Maximum Points After Enemy Battles
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-points-after-enemy-battles)
Canonical: https://scaleengineer.com/dsa/problems/maximum-points-after-enemy-battles
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
**Companies:** [Rubrik](https://scaleengineer.com/companies/rubrik)
---
## Problem
You are given an integer array `enemyEnergies` denoting the energy values of various enemies.

You are also given an integer `currentEnergy` denoting the amount of energy you have initially.

You start with 0 points, and all the enemies are unmarked initially.

You can perform **either** of the following operations **zero** or multiple times to gain points:

* Choose an **unmarked** enemy, `i`, such that `currentEnergy >= enemyEnergies[i]`. By choosing this option:  
  * You gain 1 point.
  * Your energy is reduced by the enemy's energy, i.e. `currentEnergy = currentEnergy - enemyEnergies[i]`.
* If you have **at least** 1 point, you can choose an **unmarked** enemy, `i`. By choosing this option:  
  * Your energy increases by the enemy's energy, i.e. `currentEnergy = currentEnergy + enemyEnergies[i]`.
  * The enemy `i` is **marked**.

Return an integer denoting the **maximum** points you can get in the end by optimally performing operations.

**Example 1:**

**Input:** enemyEnergies = \[3,2,2\], currentEnergy = 2

**Output:** 3

**Explanation:**

The following operations can be performed to get 3 points, which is the maximum:

* First operation on enemy 1: `points` increases by 1, and `currentEnergy` decreases by 2\. So, `points = 1`, and `currentEnergy = 0`.
* Second operation on enemy 0: `currentEnergy` increases by 3, and enemy 0 is marked. So, `points = 1`, `currentEnergy = 3`, and marked enemies = `[0]`.
* First operation on enemy 2: `points` increases by 1, and `currentEnergy` decreases by 2\. So, `points = 2`, `currentEnergy = 1`, and marked enemies = `[0]`.
* Second operation on enemy 2: `currentEnergy` increases by 2, and enemy 2 is marked. So, `points = 2`, `currentEnergy = 3`, and marked enemies = `[0, 2]`.
* First operation on enemy 1: `points` increases by 1, and `currentEnergy` decreases by 2\. So, `points = 3`, `currentEnergy = 1`, and marked enemies = `[0, 2]`.

**Example 2:**

**Input:** enemyEnergies = \[2\], currentEnergy = 10

**Output:** 5

**Explanation:** 

Performing the first operation 5 times on enemy 0 results in the maximum number of points.

**Constraints:**

* `1 <= enemyEnergies.length <= 105`
* `1 <= enemyEnergies[i] <= 109`
* `0 <= currentEnergy <= 109`

# Approaches
## Brute-Force with Backtracking
This approach attempts to solve the problem by exploring all possible sequences of operations. It uses a recursive backtracking method to try every valid move at each state, which is defined by the current energy, current points, and the set of unmarked enemies. The goal is to find the path of operations that results in the maximum number of points.
**Time:** O(Exponential) · **Space:** O(Exponential)
**Pros:** Guaranteed to find the optimal solution if it could be implemented and run to completion.
**Cons:** Extremely high time complexity, likely exponential, making it infeasible for the given constraints.; The state space for memoization is too large due to the `currentEnergy` parameter, which can be up to 10^9 plus other energies.; The logic is very complex to implement correctly, especially handling the fact that gaining a point does not mark the enemy, which can lead to infinite recursion if not bounded properly.
### Explanation
A brute-force solution would involve a recursive function that explores the entire state space of the problem. A state can be defined by `(currentEnergy, points, unmarked_enemies)`. From any given state, we can transition to a new state by applying one of the two allowed operations on any of the unmarked enemies.

For example, a function `solve(currentEnergy, points, unmarked_mask)` would be called recursively. Inside this function, we would loop through all enemies. If an enemy `i` is unmarked, we would explore two branches:
1.  **Gain Point:** If `currentEnergy` is sufficient, we calculate the state after gaining a point from enemy `i` and recurse. A major complexity here is that the enemy remains unmarked, so we could attack it again. A pure recursive approach would need a way to decide how many times to attack before trying another operation.
2.  **Gain Energy:** If `points > 0`, we calculate the state after absorbing energy from enemy `i` (which marks it) and recurse.

The maximum value from all these recursive explorations would be the answer. Due to the enormous state space and branching factor, this approach is not practical and would time out on all but the smallest inputs.

```java
// NOTE: The following is a conceptual representation. A correct and runnable
// brute-force solution is non-trivial due to the problem's nature (e.g., infinite loops).
class Solution {
    // This map would be for memoization, but the state space is too large.
    // A proper key would need to include energy, points, and the mask.
    Map<String, Long> memo = new HashMap<>();

    public long maximumPoints(int[] enemyEnergies, int currentEnergy) {
        // The problem's constraints and mechanics make a simple backtracking approach infeasible.
        // The key issue is deciding how many times to perform Operation 1 on an enemy before
        // switching to another operation. This leads to an infinite decision tree if not bounded.
        // A practical implementation is omitted due to its complexity and inefficiency.
        return 0; // Placeholder
    }
}
```
### Algorithm
1. Define a recursive function, let's say `solve(currentEnergy, points, unmarked_mask)`, where `unmarked_mask` is a bitmask representing the set of unmarked enemies.
2. The base case for the recursion is when no more operations can be performed. The function returns the current number of points.
3. In each recursive call, iterate through all unmarked enemies.
4. For each unmarked enemy `i`:
    a. **Try Operation 1 (Gain Point):** If `currentEnergy >= enemyEnergies[i]`, we can potentially gain a point. Since this operation can be repeated on the same unmarked enemy, this branch leads to complex subproblems (how many times to attack?). A simplified brute-force might assume you attack once and mark it, which is not per the problem but makes it tractable for a simple recursion.
    b. **Try Operation 2 (Gain Energy):** If `points > 0`, make a recursive call with updated energy (`currentEnergy + enemyEnergies[i]`) and an updated mask (marking enemy `i`).
5. The function would return the maximum value obtained from all possible recursive paths.
6. To handle the complexity of repeated attacks, the state would need to include `currentEnergy`, making memoization difficult.

## Greedy Approach with Sorting
This approach is based on the greedy insight that to maximize points, we should always spend energy on the weakest enemy and gain energy from the strongest available enemy. By sorting the `enemyEnergies` array, we can use a two-pointer technique to efficiently manage this process.
**Time:** O(N log N) · **Space:** O(log N) or O(N)
**Pros:** Much more efficient than a brute-force approach.; Follows a clear, greedy logic that is easier to reason about than backtracking.; Correctly solves the problem within the given time limits.
**Cons:** The O(N log N) time complexity from sorting is not the most optimal.; The loop logic, while correct, is more complex than the most optimal solution.
### Explanation
The strategy is to use a two-pointer system on the sorted `enemyEnergies` array. A `low` pointer tracks the weakest enemy to fight for points, and a `high` pointer tracks the strongest enemy to sacrifice for energy.

First, we sort the `enemyEnergies` array. If our initial energy is less than the weakest enemy's energy, we can't do anything, so we return 0. Otherwise, we enter a loop. In each phase of the loop, we first use our current energy to gain as many points as possible from the weakest enemy (at index `low`). After we've exhausted our energy (i.e., `currentEnergy < enemyEnergies[low]`), we check if we have any points and if there are stronger enemies left (i.e., `low < high`). If so, we sacrifice the strongest available enemy (at index `high`) to replenish our energy. This cycle of spending energy on the weak and gaining from the strong continues until we can no longer make progress.

```java
import java.util.Arrays;

class Solution {
    public long maximumPoints(int[] enemyEnergies, int currentEnergy) {
        Arrays.sort(enemyEnergies);
        
        if (currentEnergy < enemyEnergies[0]) {
            return 0;
        }
        
        long points = 0;
        int low = 0;
        int high = enemyEnergies.length - 1;
        long currentEnergyLong = currentEnergy;
        
        while (low <= high) {
            if (currentEnergyLong >= enemyEnergies[low]) {
                // Spend energy on the weakest enemy to gain points
                long pointsGained = currentEnergyLong / enemyEnergies[low];
                points += pointsGained;
                currentEnergyLong %= enemyEnergies[low];
            }
            
            // Check if we can gain more energy by sacrificing the strongest enemy
            if (points > 0 && low < high) {
                currentEnergyLong += enemyEnergies[high];
                high--;
            } else {
                // No more progress can be made
                break;
            }
        }
        
        return points;
    }
}
```
### Algorithm
1. Sort the `enemyEnergies` array in non-decreasing order.
2. Initialize `points = 0`, `low = 0`, `high = enemyEnergies.length - 1`, and `currentEnergyLong = currentEnergy`.
3. If `currentEnergy < enemyEnergies[0]`, we cannot defeat even the weakest enemy, so return 0.
4. Start a loop that continues as long as `low <= high`.
5. Inside the loop, if `currentEnergyLong >= enemyEnergies[low]`, spend energy to gain points from the weakest enemy. Calculate how many times you can defeat it: `pointsGained = currentEnergyLong / enemyEnergies[low]`, add this to `points`, and update `currentEnergyLong` with the remainder.
6. If after gaining points, you have `points > 0` and there are stronger enemies left (`low < high`), use Operation 2 on the strongest enemy: `currentEnergyLong += enemyEnergies[high]` and decrement `high`.
7. If you cannot make any more progress (not enough energy to fight the weakest enemy and either no points to refuel or no stronger enemies to sacrifice), break the loop.
8. Return the total `points` accumulated.

## Optimal Greedy Approach with Linear Scan
This is the most efficient approach. It builds upon the greedy strategy but realizes that the intermediate steps of gaining and spending energy can be abstracted away. The core idea is that we can effectively pool all the energy from our initial amount and all enemies except the weakest one. This entire energy pool can then be spent to repeatedly fight the weakest enemy to maximize points.
**Time:** O(N) · **Space:** O(1)
**Pros:** Most efficient solution with O(N) time complexity.; Simple and direct implementation, avoiding complex loops or data structures.; Uses constant extra space.
**Cons:** The logic, while simple to implement, might seem non-obvious without first understanding the underlying greedy strategy that justifies it.
### Explanation
The optimal strategy is a refined greedy approach. To maximize points, we should always use the enemy with the minimum energy cost (`minEnergy`) for gaining points (Operation 1). To maximize our energy supply, we should use all other enemies for gaining energy (Operation 2). This is possible if we can get at least one point to start, which requires `currentEnergy >= minEnergy`.

If we can start, we can imagine a process where we gain one point from the weakest enemy, then use that point to start a cycle of sacrificing stronger enemies for energy and using that energy to gain more points from the weakest enemy. The net result of this process is equivalent to pooling all available energy sources (initial energy + energy from all enemies except the weakest) and spending it all on the weakest enemy.

The calculation is straightforward:
1. Find `minEnergy` and the `totalEnergySum` of the array in one pass.
2. If `currentEnergy < minEnergy`, return 0.
3. Otherwise, the total energy we can leverage is `currentEnergy + (totalEnergySum - minEnergy)`.
4. The max points are `(currentEnergy + totalEnergySum - minEnergy) / minEnergy`.

This avoids sorting and provides a linear time solution.

```java
class Solution {
    public long maximumPoints(int[] enemyEnergies, int currentEnergy) {
        int minEnergy = Integer.MAX_VALUE;
        long totalEnergySum = 0;

        // Find the minimum energy and the total sum in one pass
        for (int energy : enemyEnergies) {
            minEnergy = Math.min(minEnergy, energy);
            totalEnergySum += energy;
        }
        
        // If we can't even defeat the weakest enemy initially, we can't get any points.
        if (currentEnergy < minEnergy) {
            return 0;
        }
        
        // The total energy we can pool is our current energy plus all energies from
        // sacrificing enemies. We sacrifice all enemies except the one with minEnergy.
        long availableForPoints = (long)currentEnergy + totalEnergySum - minEnergy;
        
        // The number of points is the total available energy divided by the cost of one point.
        return availableForPoints / minEnergy;
    }
}
```
### Algorithm
1. Find the minimum energy value, `minEnergy`, in the `enemyEnergies` array.
2. If `currentEnergy < minEnergy`, it's impossible to gain the first point, so return 0.
3. Calculate the sum of all energies in the array, let's call it `totalEnergySum`.
4. The core insight is that we can use all enemies except the weakest one to fuel our energy. The total energy from these sacrifices is `totalEnergySum - minEnergy`.
5. The total energy pool we can use to score points is our initial `currentEnergy` plus the energy from all sacrificed enemies: `availableEnergy = currentEnergy + totalEnergySum - minEnergy`.
6. The maximum number of points is this total available energy divided by the cost of one point, which is `minEnergy`. So, the result is `availableEnergy / minEnergy`.
7. This can all be computed in a single pass through the array.

# Solutions
### Java

```java
class Solution {
public
  long maximumPoints(int[] enemyEnergies, int currentEnergy) {
    Arrays.sort(enemyEnergies);
    if (currentEnergy < enemyEnergies[0]) {
      return 0;
    }
    long ans = 0;
    for (int i = enemyEnergies.length - 1; i >= 0; --i) {
      ans += currentEnergy / enemyEnergies[0];
      currentEnergy %= enemyEnergies[0];
      currentEnergy += enemyEnergies[i];
    }
    return ans;
  }
};

```

### CPP

```cpp
class Solution {
public:
  long long maximumPoints(vector<int> &enemyEnergies, int currentEnergy) {
    sort(enemyEnergies.begin(), enemyEnergies.end());
    if (currentEnergy < enemyEnergies[0]) {
      return 0;
    }
    long long ans = 0;
    for (int i = enemyEnergies.size() - 1; i >= 0; --i) {
      ans += currentEnergy / enemyEnergies[0];
      currentEnergy %= enemyEnergies[0];
      currentEnergy += enemyEnergies[i];
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maximumPoints(self, enemyEnergies: List[int], currentEnergy: int) -> int: enemyEnergies . sort() if currentEnergy < enemyEnergies[0]: return 0 ans = 0 for i in range(len(enemyEnergies) - 1, - 1, - 1): ans += currentEnergy // enemyEnergies[0] currentEnergy %= enemyEnergies[0] currentEnergy += enemyEnergies[i] return ans

```