Skip to main content
Talentd

Maximum Points After Enemy Battles - Solution & Explanation

MediumArrayGreedy11 min readAsked at: Rubrik
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given a list of enemies where each enemy requires a certain amount of energy to defeat. Defeating an enemy costs energy but earns points. Some strategies also allow trading points to regain energy. The goal is to maximize the total points after a sequence of enemy battles.

Approach 1: Greedy with Sorting and Two Pointers (O(n log n) time, O(1) space)

The optimal strategy follows a greedy idea similar to resource management problems. Sort the enemy energy requirements first. Use two pointers: one starting from the weakest enemy and one from the strongest. If you have enough energy, defeat the weakest enemy to gain a point and reduce your energy. If you cannot defeat any enemy but already have points, trade one point to regain energy by interacting with the strongest remaining enemy. This keeps weaker enemies available for cheap points while using stronger enemies as energy recovery when necessary. Sorting enables efficient selection of cheapest and most expensive enemies, making this approach O(n log n) time with constant extra space.

This approach relies on greedy decision making: always gain points using the cheapest enemy first, and only sacrifice points when it unlocks future wins. The pattern appears frequently in Greedy optimization problems and resource allocation tasks involving Array manipulation.

Approach 2: Dynamic Programming (O(n * E) time, O(n * E) space)

A dynamic programming formulation explores all valid battle sequences. Define a DP state representing the maximum points achievable using the first i enemies with a given remaining energy E. For each enemy, you can either defeat it (if energy allows) to gain a point and reduce energy, or skip/trade depending on the rules that restore energy at the cost of points. Transition states update the best achievable score while tracking energy changes.

This approach systematically evaluates every feasible decision path. It works well when constraints on energy are small enough to keep the DP table manageable. However, its state space grows with both enemy count and energy values, making it slower and more memory-intensive than the greedy solution.

The DP formulation helps verify correctness and can be useful when greedy conditions are unclear. It also demonstrates how the problem can be interpreted as a state transition problem common in Dynamic Programming.

Recommended for interviews: The greedy sorting strategy is what most interviewers expect. Recognizing that defeating weaker enemies first maximizes future flexibility is the key insight. Implementing the two-pointer technique after sorting demonstrates strong problem-solving intuition and keeps the solution clean at O(n log n) time. Discussing the DP alternative shows deeper understanding, but the greedy approach is the practical optimal solution.

Approach 1: Greedy Approach with Sorting

Sort the enemies by their energy requirement. Try to gain a point by defeating the lowest energy enemy when possible. If you cannot defeat any enemy, lend your energy to the highest energy unmarked enemy you can mark, provided you have at least one point.

The strategy involves sorting the enemy energies. A two-pointer technique is used. The left pointer is initially at the most attainable enemy and the right pointer at the most costly enemy. Whenever the energy is sufficient to defeat the enemy at the left pointer, do so to gain a point. If not, convert some points to energy by marking an unmarked enemy at the right pointer. If both options run out, the loop ends.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) without considering input storage.

Try this approach in the editor →

Approach 2: Dynamic Programming Approach

Utilize dynamic programming to keep track of achievable points given energies left or gathered. Construct a 2D DP table where row denotes use of 'current energy' and column denotes possible number of points.

The dynamic programming approach uses a 1D array to keep track of the maximum points achievable with up to the available energy. By iterating through each enemy's energy requirement, update the possible maximum points in reverse order of energies to ensure correct computations.

Code

C++

C++

Complexity

Time Complexity: O(n * e), where e is the currentEnergy at maximum, since the DP traversal across energies is performed for each enemy.
Space Complexity: O(e) due to the DP array usage.

Try this approach in the editor →

Approach 3: Greedy + Sorting

According to the problem description, we need to score by defeating enemies with the lowest energy value and increase our energy value by defeating enemies with the highest energy value and marking them.

Therefore, we can sort the enemies by their energy values, then start from the enemy with the highest energy value, always choose the enemy with the lowest energy value to score and consume energy. Next, we add the energy value of the enemy with the highest energy to our current energy and mark that enemy. Repeat the above steps until all enemies are marked.

The time complexity is O(n log n), and the space complexity is O(log n), where n is the number of enemies.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach with Sorting

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) without considering input storage.

Dynamic Programming Approach

Time Complexity: O(n * e), where e is the currentEnergy at maximum, since the DP traversal across energies is performed for each enemy.
Space Complexity: O(e) due to the DP array usage.

Greedy + Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy with Sorting and Two PointersO(n log n)O(1)Best practical solution. Efficient when enemies can be sorted and decisions depend on weakest/strongest choices.
Dynamic ProgrammingO(n * E)O(n * E)Useful when exploring all decision states or when greedy conditions are unclear.

Video Solution

3207. Maximum Points After Enemy Battles | Sorting | Greedy • Aryan Mittal • 2,269 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Maximum Points After Enemy Battles easy or hard?
Maximum Points After Enemy Battles is generally considered a Medium difficulty problem. The implementation is straightforward once the greedy insight is recognized, but identifying the correct strategy and managing the two-pointer decisions can take some practice.
Maximum Points After Enemy Battles Python/Java solution
Python and Java implementations typically sort the enemy array and maintain two pointers. The algorithm increases points by defeating weaker enemies and conditionally sacrifices a point to regain energy from stronger enemies, ensuring the maximum achievable score.
How to solve Maximum Points After Enemy Battles in O(n log n)?
First sort the enemy energy array. Use two pointers: the left pointer targets the weakest enemy to gain points, while the right pointer targets the strongest enemy to regain energy when needed. Continue defeating weak enemies whenever energy allows and trade points only when it unlocks additional wins.
What is the best approach for Maximum Points After Enemy Battles?
The most efficient approach is a greedy strategy with sorting. Sort enemies by required energy, defeat the weakest enemies first to accumulate points, and if energy runs out, trade a point to regain energy using the strongest remaining enemy. This approach runs in O(n log n) time due to sorting and uses O(1) extra space.
Is Maximum Points After Enemy Battles asked at Google/Amazon/Meta?
Problems based on greedy resource allocation and two-pointer strategies appear frequently in interviews at companies like Amazon, Google, and Meta. This problem closely resembles classic greedy interview questions such as Bag of Tokens, making it relevant preparation.
What data structure is used in Maximum Points After Enemy Battles?
The core data structure is an array combined with sorting and a two-pointer technique. The algorithm repeatedly accesses the smallest and largest remaining values to decide whether to gain points or recover energy.
What is the time complexity of Maximum Points After Enemy Battles?
The optimal greedy solution runs in O(n log n) time because the enemy list must be sorted. After sorting, a two-pointer scan processes each enemy at most once. Space complexity is O(1) if sorting is done in place.

Ready to solve this problem?

Practice Maximum Points After Enemy Battles with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays