Maximum Points After Enemy Battles

Medium

Rubrik

6 views

Topics:

ArraysGreedy Algorithms

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 <= 10⁵
1 <= enemyEnergies[i] <= 10⁹
0 <= currentEnergy <= 10⁹

Try coding it in LeetCode

Maximum Points After Enemy Battles

Medium

Rubrik

6 views

Topics:

ArraysGreedy Algorithms

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 <= 10⁵
1 <= enemyEnergies[i] <= 10⁹
0 <= currentEnergy <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for enemyStrengths, yourStrengths, and energy? Are they all non-negative integers?
What should I return if it's impossible to defeat any enemies with the given energy and strengths? Should I return 0, or is there an error condition I should handle?
Are the lengths of the `enemyStrengths` and `yourStrengths` arrays guaranteed to be the same?
Can the `enemyStrengths` or `yourStrengths` arrays be empty or null? If so, what should I return?
If multiple combinations of enemy battles yield the same maximum points, is any one of them acceptable?

Brute Force Solution

Approach

The brute force method involves exploring every possible combination of battle choices to determine the one yielding the maximum points. We essentially simulate every scenario by considering all possible sequences of fighting or skipping enemies. This guarantees that we will find the best possible outcome, albeit inefficiently.

Here's how the algorithm would work step-by-step:

Start by considering the first enemy. We have two options: fight it or skip it.
For each of these two options, consider the next enemy. Again, we can either fight it or skip it.
Continue this process for all enemies. At each step, we branch out, creating two new possibilities for each existing one.
Eventually, we will reach the end of the list of enemies for each possible path we've created.
For each of these complete paths (representing a specific combination of fighting and skipping enemies), calculate the total points earned.
Compare the total points earned for all the different paths.
The path with the highest total points represents the optimal strategy, and that value is the answer.

Code Implementation

def max_points_after_enemy_battles_brute_force(enemies):
    max_points = 0

    def calculate_max_points(current_index, current_points):
        nonlocal max_points

        # When we reach the end, update max points
        if current_index == len(enemies):
            max_points = max(max_points, current_points)
            return

        # Option 1: Fight the enemy
        # Recursively call with updated index and points
        calculate_max_points(current_index + 1, current_points + enemies[current_index])

        # Option 2: Skip the enemy
        # Recursively call with updated index and same points
        calculate_max_points(current_index + 1, current_points)

    calculate_max_points(0, 0)
    return max_points

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach explores all possible combinations of fighting or skipping enemies. For each enemy, we have two choices: fight or skip. With n enemies, this leads to 2 * 2 * ... * 2 (n times) possible scenarios. Therefore, the number of operations grows exponentially with the input size n. The total operations approximate to 2^n, resulting in a time complexity of O(2^n).

Space Complexity

O(N) – The brute force solution explores every possible combination of fighting or skipping enemies using recursion. In the worst case, where we skip or fight each enemy, the depth of the recursion will be N, where N is the number of enemies. Each recursive call adds a new frame to the call stack, so the maximum space used by the call stack is proportional to the depth of the recursion, resulting in O(N) auxiliary space.

Optimal Solution

Approach

We want to maximize points gained by choosing which enemies to battle. The trick is to recognize that we should always battle the weakest enemies first if we can defeat them, maximizing our chances to defeat stronger ones later. We also need to consider the constraint that we must battle consecutively.

Here's how the algorithm would work step-by-step:

First, sort the enemies from weakest to strongest, based on the points you lose if you fail to defeat them.
Then, go through this sorted list. For each enemy, check if you have enough strength to defeat them.
If you can defeat the enemy, battle them, increase your total points, and decrease your strength by the amount they will decrease your strength.
If you cannot defeat the enemy, skip them. Since we sorted by how much strength we lose if we fail, this is the best way to avoid big losses.
The problem requires that we battle consecutively so if you cannot defeat the next enemy, start the problem again by skipping that enemy. This essentially tests all segments of enemies.
Continue doing this for each enemy until you've gone through the entire list of enemies or can no longer defeat any more enemies.
Keep track of the maximum points you gained by trying out all valid start points within the list of enemies.
The highest total points you get from any of these strategies is the maximum points you can obtain.

Code Implementation

def maximum_points_after_enemy_battles(initial_strength, enemies):
    maximum_points = 0
    number_of_enemies = len(enemies)

    for start_index in range(number_of_enemies):
        current_strength = initial_strength
        current_points = 0

        sorted_enemies = sorted(enemies, key=lambda x: x[2])
        
        for i in range(start_index, number_of_enemies):
            enemy_attack, enemy_points, strength_loss = sorted_enemies[i]

            # Check if current strength is enough to defeat the enemy.
            if current_strength > enemy_attack:
                current_strength -= enemy_attack
                current_points += enemy_points
            else:
                # If we can't defeat, check penalty. Break inner loop
                break

        maximum_points = max(maximum_points, current_points)

    return maximum_points

Big(O) Analysis

Time Complexity

O(n log n) – The dominant operation is sorting the enemies initially, which takes O(n log n) time, where n is the number of enemies. The nested loops iterate through all possible start positions and then iterate through the sorted list of enemies. While it appears to be O(n^2), the inner loop's runtime is heavily dependent on the initial strength and the enemy strengths. However, sorting takes O(n log n) and iterating across the entire sorted list multiple times from different starting points contributes a linear O(n) factor within the outer loop which is O(n). The overall complexity is therefore O(n log n + n*n) which simplifies to O(n log n), due to the sorting step being more impactful than scanning all possible subarrays.

Space Complexity

O(N) – The primary auxiliary space is used for sorting the enemies initially. Sorting algorithms like merge sort or quicksort, commonly used in library implementations, typically require O(N) auxiliary space in the worst-case, where N is the number of enemies. Although there are in-place sorting algorithms, they are typically not used due to performance considerations for general-purpose sorting. Additionally, constant space is used for variables like the current points and strength, but this is insignificant compared to the space used for sorting, hence O(N).

Edge Cases

Case	How to Handle
enemyStrengths or yourStrengths is null or empty	Return 0 immediately as no battles are possible.
enemyStrengths and yourStrengths have different lengths	Return 0 as a unit is required for each enemy battle; the problem is ill-defined.
energy is negative	Treat negative energy as 0, disallowing any battles to occur (return 0).
All yourStrengths are greater than energy	Return 0, as no battle is possible due to insufficient energy.
All enemyStrengths are very small, yourStrengths are small, energy is very large	Maximize point collection until energy depletion, handled correctly by optimal selection strategy.
enemyStrengths and yourStrengths are very large (max int) and energy is very large	Potential integer overflow during point calculation can be avoided by careful type casting to long if using Java/C++ during intermediate calculations.
Some enemyStrengths are zero	Battling enemies with zero strength results in a no-cost point gain, the optimal strategy should account for this.
Your unit strengths are highly variable, some very small, some very large	The optimal strategy needs to prioritize smaller strengths to enable more battles which maximizes point accumulation.