Skip to main content
Talentd

Minimum Hours of Training to Win a Competition - Solution & Explanation

EasyArrayGreedy17 min readAsked at: Amazon
Practice this problem

Problem Statement

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.length
  • 1 <= n <= 100
  • 1 <= initialEnergy, initialExperience, energy[i], experience[i] <= 100

Approach Overview

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

Approach 1: Greedy Training Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Greedy + Simulation

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.

  • If x leq dx, then we need to train for dx + 1 - x hours to increase our energy to dx + 1.
  • If y leq dy, then we need to train for dy + 1 - y hours to increase our experience to dy + 1.
  • Then, we subtract 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).

Code

PythonJavaC++GoTypeScriptRustC

Python

Java

C++

Go

TypeScript

Rust

C

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Training Approach

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.

Greedy + Simulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Naive Simulation with Incremental TrainingO(n + k)O(1)Useful for understanding the mechanics of the problem and straightforward simulation
Greedy Training CalculationO(n)O(1)Optimal solution for interviews and production code; calculates minimal required training directly

Video Solution

2383. Minimum Hours of Training to Win a Competition || leetcode Weekly 307|| Leetcode Easy • BinaryMagic • 677 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Minimum Hours of Training to Win a Competition easy or hard?
Minimum Hours of Training to Win a Competition is classified as an Easy problem on LeetCode. The challenge lies in recognizing the greedy insight: energy depends on the total sum, while experience must be adjusted step by step during iteration.
Minimum Hours of Training to Win a Competition Python/Java solution
In Python or Java, iterate through the energy and experience arrays while tracking your current stats and accumulated training hours. Calculate the required energy training using the total energy sum, then greedily adjust experience before each fight. The implementation runs in O(n) time with constant extra space.
How to solve Minimum Hours of Training to Win a Competition in O(n)?
First compute the total energy required by summing the energy array and ensure the initial energy is at least total + 1. Then iterate through each opponent’s experience. If your experience is less than or equal to the opponent’s, train the difference plus one hour. After each win, increase your experience by the opponent’s experience value.
What is the best approach for Minimum Hours of Training to Win a Competition?
The best approach is a greedy training calculation. Compute the total energy required to defeat all opponents and ensure your initial energy is greater than that sum. Then iterate through the experience array and train only when your experience is not strictly greater than the current opponent. This produces the minimum required training in O(n) time and O(1) space.
Is Minimum Hours of Training to Win a Competition asked at Google/Amazon/Meta?
Problems involving greedy resource management and sequential constraints appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact question may not always appear, its pattern—ensuring a running value stays above a threshold while processing an array—is common in interview problem sets.
What data structure is used in Minimum Hours of Training to Win a Competition?
The problem primarily uses arrays to store opponent energy and experience values. The algorithm processes these arrays sequentially while maintaining running totals and current stats. No advanced data structures are required beyond basic variables.
What is the time complexity of Minimum Hours of Training to Win a Competition?
The optimal solution runs in O(n) time where n is the number of opponents. You perform a single pass to sum the energy requirements and another pass (or the same pass) to check experience constraints. Space complexity is O(1) because only a few variables are used.

Ready to solve this problem?

Practice Minimum Hours of Training to Win a Competition with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays