Maximum Points After Enemy Battles - Solution & Explanation

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.