Problem Description

You are given an integer array enemyEnergies representing the energy values of various enemies. You also have an integer currentEnergy, representing the amount of energy you start with. Initially, you have 0 points, and all enemies are unmarked.

You can use either of the following operations, zero or multiple times, to gain points:

1. Select an unmarked enemy i if currentEnergy >= enemyEnergies[i]. By doing this:

   • Gain 1 point.
   • Reduce your energy by the enemy's energy: currentEnergy = currentEnergy - enemyEnergies[i].

2. If you have at least 1 point, select an unmarked enemy i. By doing this:

   • Increase your energy by the enemy's energy: currentEnergy = currentEnergy + enemyEnergies[i].
   • The enemy i is marked.

Your task is to return an integer representing the maximum points you can achieve by optimally performing these operations.

Intuition

The problem revolves around gaining the maximum number of points by strategically managing your energy and the marking of enemies. The solution leverages a greedy approach with sorting.

Here’s the thought process:

1. Sort the Enemies: Start by sorting the enemies based on their energy values. This allows you to always assess minimal energy first, which is crucial as it lets you defeat weaker enemies easily and accumulate points without exhausting all your energy readily.

2. Maximize Points with Lowest Energy Enemies: By defeating enemies from the lowest energy value to the highest, you are ensuring that you gather more points by marking weaker enemies first since they cost less energy.

3. Energy Management and Recovery: Use the points you accumulate to potentially mark stronger enemies, thereby recovering energy. This is an important part of the strategy because marking higher energy enemies can replenish your energy, allowing you to defeat additional weaker foes and further maximize points.

In essence, the approach ensures a balance between utilizing minimal energy to gain points and strategically recovering energy to sustain the fight. This looping action continues until all foes are marked or no further actions can be taken, ensuring the highest score possible.

Learn more about Greedy patterns.

Solution Approach

In this solution, we adopt a greedy approach combined with sorting to maximize the points:

1. Sort the Array: Begin by sorting enemyEnergies in ascending order. This ordering is crucial since it allows you to deal with the enemies demanding the least energy first.

2. Iterate Over Enemies: Utilize a loop to examine each enemy's energy value from low to high. For each enemy:

   • Attack with Sufficient Energy: If the currentEnergy is greater than or equal to an enemy's energy, use the attack operation. This increases your points by 1 and reduces currentEnergy by the enemy's energy.

   • Energy Recovery with Points: If you have any points, consider if marking (i.e., sacrificing a point to regain energy from a marked enemy) is beneficial. This strategy involves recovering energy using the enemy with the highest energy value you have encountered and not yet marked.

3. Maximize Points: The loop continues until you can neither defeat another enemy nor does marking provide a strategic benefit. Throughout this process, ensure that energy usage is optimized to achieve the maximum number of points.

The implemented code logic in Python can be summarized as follows:

class Solution:
    def maximumPoints(self, enemyEnergies: List[int], currentEnergy: int) -> int:
        enemyEnergies.sort()  # Step 1: Sort the enemies by energy requirement
        ans = 0  # Initialize points
      
        left, right = 0, len(enemyEnergies) - 1  # Two pointers for smallest and largest

        # Step 2: Use a [greedy](/problems/greedy_intro) strategy to maximize points
        while left <= right:
            if currentEnergy >= enemyEnergies[left]:
                # Attack to gain a point if energy allows
                currentEnergy -= enemyEnergies[left]
                ans += 1
                left += 1
            elif ans > 0:
                # Use a point to regain energy if possible
                currentEnergy += enemyEnergies[right]
                ans -= 1
                right -= 1
            else:
                # Break when no more progress can be made
                break

        return ans

This solution effectively balances point accumulation through attack operations and strategic energy recovery through marking, ensuring the optimal strategy is employed throughout. It handles efficient computation using sorting and while-loop based greedy checking to assure maximum points accumulation.

Example Walkthrough

Let's take a concrete example to illustrate the solution approach. Suppose we have:

• enemyEnergies = [2, 3, 4, 5]
• currentEnergy = 5

We aim to determine the maximum points we can achieve. Here's how the solution unfolds step-by-step:

1. Sort the Array: Start by sorting enemyEnergies, but since [2, 3, 4, 5] is already sorted, we proceed with the same array.

2. Initialization:

   • Initialize ans = 0 to keep track of points.
   • Use two pointers, left = 0 (pointing to the smallest energy enemy) and right = 3 (pointing to the largest energy enemy).

3. Iterate Over Enemies:

   • First Loop Iteration:

     • currentEnergy = 5, enemyEnergies[left] = 2. Since 5 >= 2, use the attack operation:
       • Gain 1 point (ans = 1).
       • Reduce currentEnergy by 2 (currentEnergy = 3).
       • Move left to the next enemy (left = 1).

   • Second Loop Iteration:

     • currentEnergy = 3, enemyEnergies[left] = 3. Since 3 >= 3, use the attack operation:
       • Gain another point (ans = 2).
       • Reduce currentEnergy by 3 (currentEnergy = 0).
       • Move left to the next enemy (left = 2).

   • Third Loop Iteration:

     • currentEnergy = 0, unable to attack enemyEnergies[left] = 4.
     • Utilize a point to increase energy. Sacrifice 1 point (ans = 1) and mark the enemy with the highest energy (enemyEnergies[right] = 5).
     • Increase currentEnergy by 5 (currentEnergy = 5).
     • Move right to the previous enemy (right = 2).

   • Fourth Loop Iteration:

     • currentEnergy = 5, enemyEnergies[left] = 4. Since 5 >= 4, use the attack operation:
       • Gain a point (ans = 2).
       • Reduce currentEnergy by 4 (currentEnergy = 1).
       • Move left to the next enemy (left = 3).

4. Break Condition:

   • Cannot perform more actions since currentEnergy < enemyEnergies[left] and no more points to use for energy recovery.

The maximum points achieved is 2. This process strategically balances gaining points with attacks and recovering energy when needed, ensuring the optimal result.

Solution Implementation

Time and Space Complexity

The time complexity of the code is O(n log n) due to the sorting of enemyEnergies. The space complexity is O(log n) because of the stack space used by the sorting algorithm, which is often implemented as a quick sort or merge sort.

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