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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


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

1
2
3
4
5
6
7
8
9


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 <= 10^5
  • 1 <= enemyEnergies[i] <= 10^9
  • 0 <= currentEnergy <= 10^9

Solution

Method 1 – Greedy with Two Pointers

Intuition

To maximize points, always defeat the weakest enemy you can afford to gain points, and if you run out of energy but have points, use a point to regain energy from the strongest remaining enemy. This is similar to the “bag of tokens” problem and can be solved greedily with sorting and two pointers.

Approach

  1. Sort enemyEnergies in ascending order.
  2. Use two pointers: l (start) and r (end).
  3. While l <= r:
    • If currentEnergy >= enemyEnergies[l], defeat enemy at l, gain 1 point, lose energy, move l forward.
    • Else if you have at least 1 point and l < r, use a point to gain energy from enemy at r, lose 1 point, gain energy, move r backward.
    • Else, break.
  4. Track and return the maximum points achieved.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int maxPoints(vector<int>& enemyEnergies, int currentEnergy) {
        sort(enemyEnergies.begin(), enemyEnergies.end());
        int l = 0, r = enemyEnergies.size() - 1, points = 0, maxPoints = 0;
        while (l <= r) {
            if (currentEnergy >= enemyEnergies[l]) {
                currentEnergy -= enemyEnergies[l++];
                points++;
                maxPoints = max(maxPoints, points);
            } else if (points > 0 && l < r) {
                currentEnergy += enemyEnergies[r--];
                points--;
            } else {
                break;
            }
        }
        return maxPoints;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

func maxPoints(enemyEnergies []int, currentEnergy int) int {
    sort.Ints(enemyEnergies)
    l, r := 0, len(enemyEnergies)-1
    points, maxPoints := 0, 0
    for l <= r {
        if currentEnergy >= enemyEnergies[l] {
            currentEnergy -= enemyEnergies[l]
            l++
            points++
            if points > maxPoints {
                maxPoints = points
            }
        } else if points > 0 && l < r {
            currentEnergy += enemyEnergies[r]
            r--
            points--
        } else {
            break
        }
    }
    return maxPoints
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int maxPoints(int[] enemyEnergies, int currentEnergy) {
        Arrays.sort(enemyEnergies);
        int l = 0, r = enemyEnergies.length - 1, points = 0, maxPoints = 0;
        while (l <= r) {
            if (currentEnergy >= enemyEnergies[l]) {
                currentEnergy -= enemyEnergies[l++];
                points++;
                maxPoints = Math.max(maxPoints, points);
            } else if (points > 0 && l < r) {
                currentEnergy += enemyEnergies[r--];
                points--;
            } else {
                break;
            }
        }
        return maxPoints;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    fun maxPoints(enemyEnergies: IntArray, currentEnergy: Int): Int {
        val arr = enemyEnergies.sorted()
        var l = 0
        var r = arr.size - 1
        var points = 0
        var maxPoints = 0
        var energy = currentEnergy
        while (l <= r) {
            if (energy >= arr[l]) {
                energy -= arr[l++]
                points++
                maxPoints = maxOf(maxPoints, points)
            } else if (points > 0 && l < r) {
                energy += arr[r--]
                points--
            } else {
                break
            }
        }
        return maxPoints
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def maxPoints(self, enemyEnergies: list[int], currentEnergy: int) -> int:
        arr = sorted(enemyEnergies)
        l, r = 0, len(arr) - 1
        points = maxPoints = 0
        while l <= r:
            if currentEnergy >= arr[l]:
                currentEnergy -= arr[l]
                l += 1
                points += 1
                maxPoints = max(maxPoints, points)
            elif points > 0 and l < r:
                currentEnergy += arr[r]
                r -= 1
                points -= 1
            else:
                break
        return maxPoints
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
    pub fn max_points(mut enemy_energies: Vec<i32>, mut current_energy: i32) -> i32 {
        enemy_energies.sort();
        let (mut l, mut r) = (0, enemy_energies.len() - 1);
        let (mut points, mut max_points) = (0, 0);
        while l <= r {
            if current_energy >= enemy_energies[l] {
                current_energy -= enemy_energies[l];
                l += 1;
                points += 1;
                max_points = max_points.max(points);
            } else if points > 0 && l < r {
                current_energy += enemy_energies[r];
                r -= 1;
                points -= 1;
            } else {
                break;
            }
        }
        max_points
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    maxPoints(enemyEnergies: number[], currentEnergy: number): number {
        const arr = [...enemyEnergies].sort((a, b) => a - b);
        let l = 0, r = arr.length - 1;
        let points = 0, maxPoints = 0;
        while (l <= r) {
            if (currentEnergy >= arr[l]) {
                currentEnergy -= arr[l++];
                points++;
                maxPoints = Math.max(maxPoints, points);
            } else if (points > 0 && l < r) {
                currentEnergy += arr[r--];
                points--;
            } else {
                break;
            }
        }
        return maxPoints;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n) — Sorting dominates.
  • 🧺 Space complexity: O(1) — Only a few variables are used (ignoring sort output).