We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Points After Enemy Battles

Difficulty: Medium

Problem Description

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:

  1. 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].

  2. 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.

Key Insights

  • You need to balance between gaining points and marking enemies to increase energy.
  • Initially, focus on defeating enemies that you can handle with your current energy.
  • Once you have points, mark stronger enemies to maximize your energy gain.
  • Utilizing a greedy approach can help in maximizing points effectively.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the enemies. Space Complexity: O(1) - as we do not require extra space proportional to input size.

Solution

The solution involves sorting the enemyEnergies array to process the enemies in an optimal order. We will first defeat as many enemies as possible with the given currentEnergy to gain points. Then, we will utilize the points to mark enemies and regain energy for further battles. A greedy approach is used to maximize the points by always choosing the cheapest enemy available to defeat first.

Code Solutions

def maxPoints(enemyEnergies, currentEnergy):
    enemyEnergies.sort()
    points = 0
    n = len(enemyEnergies)
    
    # First, try to defeat enemies to gain points
    for energy in enemyEnergies:
        if currentEnergy >= energy:
            points += 1
            currentEnergy -= energy
            
    # Now use points to mark enemies and regain energy
    for energy in enemyEnergies:
        if points > 0:
            points -= 1
            currentEnergy += energy
            
    return points

# Example usage
print(maxPoints([3, 2, 2], 2))  # Output: 3
← Back to All Questions