Problem Description

You start with a certain amount of energy (currentEnergy) and face an array of enemies, each with their own energy value (enemyEnergies). Your goal is to maximize the points you can earn through strategic operations.

Initially, you have 0 points and all enemies are unmarked. You can perform two types of operations:

Operation 1 - Defeat an enemy to gain points:

• Choose an unmarked enemy i where your currentEnergy >= enemyEnergies[i]
• Gain 1 point
• Reduce your energy by that enemy's energy: currentEnergy = currentEnergy - enemyEnergies[i]

Operation 2 - Mark an enemy to gain energy:

• Requires at least 1 point to perform
• Choose an unmarked enemy i
• Increase your energy by that enemy's energy: currentEnergy = currentEnergy + enemyEnergies[i]
• The enemy becomes marked (cannot be used again)

The strategy involves a careful balance: you need to defeat enemies to gain points, but defeating enemies costs energy. Once you have at least 1 point, you can mark enemies to gain their energy instead, but marked enemies cannot be used for either operation again.

The solution uses a greedy approach: sort enemies by energy value, then repeatedly defeat the weakest enemy (minimum energy cost per point) while marking stronger enemies (maximum energy gain) to fuel more defeats. The algorithm continues this pattern - scoring points against the weakest enemy and absorbing energy from the strongest unmarked enemies - until all enemies are processed.

Intuition

The key insight is recognizing that once we have at least 1 point, we can freely convert any unmarked enemy into energy without losing points. This creates an interesting dynamic: we want to minimize the energy cost per point while maximizing the energy we can gather.

Think about it this way: if we have to spend energy to get points, we should spend as little as possible per point. The enemy with the smallest energy value gives us the best "exchange rate" - we get 1 point for the minimum energy cost. So we should always defeat the weakest enemy when we want to score.

On the flip side, when we mark an enemy to gain energy (which requires having at least 1 point), we should mark the strongest enemies first. Why? Because we can only mark each enemy once, and marking gives us their full energy value. By marking the strongest enemies, we maximize our energy reserves.

This leads to a clever strategy: sort the enemies by energy value. Always score points by defeating the weakest enemy (index 0), and gather energy by marking enemies starting from the strongest (working backwards from the end of the sorted array).

The algorithm becomes:

1. Get our first point by defeating the weakest enemy
2. Mark the strongest enemy to gain its energy
3. Use that energy to defeat the weakest enemy multiple times for points
4. Mark the next strongest enemy for more energy
5. Repeat until all enemies are processed

The beauty is that we're essentially converting all enemies (except the weakest one) into energy, then using all that accumulated energy to repeatedly defeat the weakest enemy for maximum points. The formula becomes: total_points = (currentEnergy + sum_of_all_other_enemies) // smallest_enemy_energy.

Learn more about Greedy patterns.

Solution Approach

The implementation follows a greedy strategy with sorting to maximize points:

Step 1: Sort the enemies

enemyEnergies.sort()

We sort the enemy energies in ascending order. This allows us to easily access the weakest enemy at index 0 and iterate through stronger enemies from the end.

Step 2: Check if we can start

if currentEnergy < enemyEnergies[0]:
    return 0

If we don't have enough energy to defeat even the weakest enemy, we can't score any points at all, so we return 0.

Step 3: Process enemies from strongest to weakest

ans = 0
for i in range(len(enemyEnergies) - 1, -1, -1):
    ans += currentEnergy // enemyEnergies[0]
    currentEnergy %= enemyEnergies[0]
    currentEnergy += enemyEnergies[i]

The loop iterates from the last index (strongest enemy) to the first (weakest enemy):

• Score points: ans += currentEnergy // enemyEnergies[0]

  • We calculate how many times we can defeat the weakest enemy with our current energy
  • Integer division // gives us the maximum number of points we can score

• Update remaining energy: currentEnergy %= enemyEnergies[0]

  • After scoring points, we keep only the remainder energy that wasn't enough for another point

• Mark and absorb energy: currentEnergy += enemyEnergies[i]

  • We mark the current enemy (from strongest to weakest) and add its energy to our pool
  • This energy will be used in the next iteration to score more points

The algorithm cleverly combines all operations: in each iteration, we first exhaust our current energy to score as many points as possible against the weakest enemy, then mark the next strongest enemy to replenish our energy for the next round. By the end, we've converted all enemies except the weakest into energy, and used all that energy to repeatedly defeat the weakest enemy for maximum points.

Example Walkthrough

Let's walk through a concrete example to see how the greedy algorithm works.

Example: currentEnergy = 5, enemyEnergies = [3, 1, 4]

Step 1: Sort the enemies After sorting: enemyEnergies = [1, 3, 4]

• Weakest enemy: 1 (index 0)
• Strongest enemies: 4, 3 (we'll process from strongest to weakest)

Step 2: Check if we can start currentEnergy (5) >= enemyEnergies[0] (1) ✓ We can defeat the weakest enemy, so we continue.

Step 3: Process enemies from strongest to weakest

Iteration 1 (i = 2, processing enemy with energy 4):

• Current energy: 5
• Score points: 5 // 1 = 5 points (defeat weakest enemy 5 times)
• Points total: 0 + 5 = 5
• Remaining energy: 5 % 1 = 0
• Mark enemy at index 2 and gain energy: 0 + 4 = 4
• New current energy: 4

Iteration 2 (i = 1, processing enemy with energy 3):

• Current energy: 4
• Score points: 4 // 1 = 4 points (defeat weakest enemy 4 times)
• Points total: 5 + 4 = 9
• Remaining energy: 4 % 1 = 0
• Mark enemy at index 1 and gain energy: 0 + 3 = 3
• New current energy: 3

Iteration 3 (i = 0, processing enemy with energy 1):

• Current energy: 3
• Score points: 3 // 1 = 3 points (defeat weakest enemy 3 times)
• Points total: 9 + 3 = 12
• Remaining energy: 3 % 1 = 0
• Mark enemy at index 0 and gain energy: 0 + 1 = 1
• New current energy: 1

Final Result: 12 points

The algorithm essentially converted the stronger enemies (3 and 4) into energy, then used all accumulated energy (5 + 4 + 3 = 12) to repeatedly defeat the weakest enemy (cost 1) for 12 total points. This is optimal because we minimized the cost per point while maximizing the energy we could gather.

Solution Implementation

Time and Space Complexity

The time complexity is O(n log n), where n is the number of enemies. This is dominated by the sorting operation enemyEnergies.sort() which takes O(n log n) time. The subsequent for loop iterates through all n elements once, performing constant time operations (division, modulo, and addition) in each iteration, contributing O(n) time. Since O(n log n) + O(n) = O(n log n), the overall time complexity is O(n log n).

The space complexity is O(log n), where n is the number of enemies. This comes from the sorting algorithm's recursive call stack. Python's sort() method typically uses Timsort, which has a worst-case space complexity of O(log n) for the recursion stack. The algorithm itself only uses a constant amount of extra space for variables like ans, i, and the modified currentEnergy, which doesn't affect the overall space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding the Energy Accumulation Logic

The Issue: A common mistake is thinking that we're "marking" enemies and somehow skipping them. In reality, the code processes EVERY enemy in the array, including the weakest one (at index 0). This leads to a subtle bug: we're effectively using the weakest enemy's energy twice - once as the target for defeating (division operation) and once as a source of energy (addition operation).

Example of the Bug:

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

After sorting: [1, 2, 3]
- Iteration 1 (i=2): score 2 points (2//1), remain 0, gain 3 energy → total: 2 points, 3 energy
- Iteration 2 (i=1): score 3 points (3//1), remain 0, gain 2 energy → total: 5 points, 2 energy  
- Iteration 3 (i=0): score 2 points (2//1), remain 0, gain 1 energy → total: 7 points, 1 energy

The problem: We're gaining energy from enemyEnergies[0] in the last iteration, but we've been using it as our target throughout. This violates the problem's constraint that each enemy can only be used once.

The Fix: Stop the loop before processing the weakest enemy:

class Solution:
    def maximumPoints(self, enemyEnergies: List[int], currentEnergy: int) -> int:
        enemyEnergies.sort()
      
        if currentEnergy < enemyEnergies[0]:
            return 0
      
        total_points = 0
      
        # Stop at index 1, not 0 - don't process the weakest enemy for energy
        for i in range(len(enemyEnergies) - 1, 0, -1):
            total_points += currentEnergy // enemyEnergies[0]
            currentEnergy %= enemyEnergies[0]
            currentEnergy += enemyEnergies[i]
      
        # Final scoring with remaining energy
        total_points += currentEnergy // enemyEnergies[0]
      
        return total_points

Pitfall 2: Not Handling Edge Cases

The Issue: When the array has only one enemy, the loop range becomes empty if we fix the first pitfall, leading to incorrect results.

Example:

enemyEnergies = [5], currentEnergy = 10
# Expected: 2 points (defeat the enemy twice)
# With fixed loop: 0 points (loop doesn't execute)

The Complete Fix: Handle single-enemy case separately:

class Solution:
    def maximumPoints(self, enemyEnergies: List[int], currentEnergy: int) -> int:
        enemyEnergies.sort()
      
        if currentEnergy < enemyEnergies[0]:
            return 0
      
        # Special case: only one enemy
        if len(enemyEnergies) == 1:
            return currentEnergy // enemyEnergies[0]
      
        total_points = 0
      
        # Mark all enemies except the weakest to gain their energy
        for i in range(len(enemyEnergies) - 1, 0, -1):
            total_points += currentEnergy // enemyEnergies[0]
            currentEnergy %= enemyEnergies[0]
            currentEnergy += enemyEnergies[i]
      
        # Final scoring with all accumulated energy
        total_points += currentEnergy // enemyEnergies[0]
      
        return total_points

This ensures we correctly handle the constraint that each enemy can only be used once while maximizing our points.