You are entering a competition, and are given two positive integers initialEnergy and initialExperience denoting your initial energy and initial experience respectively.
You are also given two 0-indexed integer arrays energy and experience, both of length n.
You will face n opponents in order. The energy and experience of the ith opponent is denoted by energy[i] and experience[i] respectively. When you face an opponent, you need to have both strictly greater experience and energy to defeat them and move to the next opponent if available.
Defeating the ith opponent increases your experience by experience[i], but decreases your energy by energy[i].
Before starting the competition, you can train for some number of hours. After each hour of training, you can either choose to increase your initial experience by one, or increase your initial energy by one.
Return the minimum number of training hours required to defeat all n opponents.
Example 1:
Input: initialEnergy = 5, initialExperience = 3, energy = [1,4,3,2], experience = [2,6,3,1] Output: 8 Explanation: You can increase your energy to 11 after 6 hours of training, and your experience to 5 after 2 hours of training. You face the opponents in the following order: - You have more energy and experience than the 0th opponent so you win. Your energy becomes 11 - 1 = 10, and your experience becomes 5 + 2 = 7. - You have more energy and experience than the 1st opponent so you win. Your energy becomes 10 - 4 = 6, and your experience becomes 7 + 6 = 13. - You have more energy and experience than the 2nd opponent so you win. Your energy becomes 6 - 3 = 3, and your experience becomes 13 + 3 = 16. - You have more energy and experience than the 3rd opponent so you win. Your energy becomes 3 - 2 = 1, and your experience becomes 16 + 1 = 17. You did a total of 6 + 2 = 8 hours of training before the competition, so we return 8. It can be proven that no smaller answer exists.
Example 2:
Input: initialEnergy = 2, initialExperience = 4, energy = [1], experience = [3] Output: 0 Explanation: You do not need any additional energy or experience to win the competition, so we return 0.
Constraints:
n == energy.length == experience.length1 <= n <= 1001 <= initialEnergy, initialExperience, energy[i], experience[i] <= 100Problem Overview: You face opponents in a fixed order. To win each match, your energy and experience must be strictly greater than the opponent’s values. After each win, energy decreases while experience increases. You can train beforehand to increase either attribute by 1 per hour. The goal is to compute the minimum training hours required to defeat all opponents.
Approach 1: Naive Simulation (While Training) (Time: O(n + k), Space: O(1))
Simulate the matches one by one and train whenever your stats are not enough. Before fighting opponent i, repeatedly increase energy until it becomes greater than energy[i]. Do the same for experience until it exceeds experience[i]. After training, simulate the fight: subtract opponent energy and add their experience to yours. This works but may perform unnecessary repeated increments, especially when a large amount of training is required. The logic is simple but inefficient compared with a direct greedy calculation.
Approach 2: Greedy Training Calculation (Time: O(n), Space: O(1))
This problem becomes straightforward once you separate energy and experience requirements. For energy, you must survive all matches sequentially, so your initial energy must be greater than the total energy consumed. Compute sum(energy). If your starting energy is not greater than this value, train exactly sum(energy) + 1 - initialEnergy hours. For experience, process opponents in order using a greedy rule: before each fight, ensure your experience is strictly greater than the opponent’s. If not, train the difference plus one hour. After winning, add the opponent’s experience to yours and continue. The greedy insight works because experience gained from earlier fights reduces training needed for later ones.
The algorithm iterates once through the arrays, making it efficient even for large inputs. Only a few integer variables are tracked, so memory usage stays constant.
Conceptually this problem mixes simple simulation with greedy decision making over an array of opponents. The greedy rule ensures you train the minimum amount necessary at each step rather than overtraining early. This pattern appears frequently in interview problems involving sequential constraints and resource accumulation, commonly categorized under greedy algorithms.
Recommended for interviews: The greedy training calculation is the expected solution. It demonstrates that you can transform a step-by-step simulation into a direct mathematical requirement for energy and a minimal incremental adjustment for experience. Mentioning the naive simulation first shows problem understanding, but implementing the greedy O(n) solution shows stronger algorithmic reasoning.
This approach starts by ensuring that you have enough energy and experience to defeat each opponent in sequence. If your current energy and experience are insufficient for an opponent, you'll calculate the additional hours of training needed to match the required levels. For each opponent, you'll update your experience after a win, and subtract the opponent's energy from your current energy.
The C implementation initializes the energy and experience levels, checks if they are sufficient to defeat each opponent, calculates any necessary training, adjusts the current experience and energy levels, and continues to the next opponent. The total training hours are summed and returned.
Time Complexity: O(n) since we iterate over each opponent once.
Space Complexity: O(1) since no additional data structures are used beyond the input and a few auxiliary variables.
Let's denote the current energy as x and the current experience as y.
Next, we traverse each opponent. For the i-th opponent, let their energy be dx and their experience be dy.
x leq dx, then we need to train for dx + 1 - x hours to increase our energy to dx + 1.y leq dy, then we need to train for dy + 1 - y hours to increase our experience to dy + 1.dx from our energy and add dy to our experience.Finally, return the answer.
The time complexity is O(n), where n is the number of opponents. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Greedy Training Approach | Time Complexity: O(n) since we iterate over each opponent once. |
| Greedy + Simulation | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Simulation with Incremental Training | O(n + k) | O(1) | Useful for understanding the mechanics of the problem and straightforward simulation |
| Greedy Training Calculation | O(n) | O(1) | Optimal solution for interviews and production code; calculates minimal required training directly |
2383. Minimum Hours of Training to Win a Competition || leetcode Weekly 307|| Leetcode Easy • BinaryMagic • 672 views views
Watch 8 more video solutions →Practice Minimum Hours of Training to Win a Competition with our built-in code editor and test cases.
Practice on FleetCode