Minimum Hours of Training to Win a Competition solution and explanation
8 more videos on this problem
2383. Minimum Hours of Training to Win a Competition || leetcode Weekly 307|| Leetcode EasyBinaryMagic · 9:49 · 677 views
2383. Minimum Hours of Training to Win a Competition |Leetcode weekly challenge| Easy | ArrayCoding Techniques with Komal | Newton School · 14:08 · 545 views
2383. Minimum Hours of Training to Win a Competition (Leetcode Easy)Programming Live with Larry · 10:39 · 510 views
2383. Minimum Hours of Training to Win a Competition || Leetcode weekly Contest || C++CS warriors · 8:46 · 507 views
[Leetcode-WC-307] Minimum Hours of Training to Win a CompetitionSandeep Kumar · 10:02 · 368 views
Leetcode Weekly contest 307 - Easy - Minimum Hours of Training to Win a CompetitionPrakhar Agrawal · 5:39 · 317 views
✅ Leetcode Weekly Contest 307 | Minimum Hours of Training to Win a Competition| Leetcode SolutionsLeetcode Hindi · 2:54 · 99 views
Leetcode Weekly Contest 307 || Minimum Hours of Training to Win a Competition || Leetcode Solutionsdecodeourmind :) · 3:08 · 62 views
Leetcode 2383. Minimum Hours of Training to Win a Competition - linear traversalCode-Yao · 10:51 · 45 views
The problem
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] <= 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.
def min_training_hours(initial_energy, initial_experience, energy, experience):
hours = 0
current_energy = initial_energy
current_experience = initial_experience
for e, exp in zip(energy, experience):
if current_energy <= e:
hours += (e - current_energy + 1)
current_energy = e + 1
if current_experience <= exp:
hours += (exp - current_experience + 1)
current_experience = exp + 1
current_energy -= e
current_experience += exp
return hours
energy = [1, 4, 3, 2]
experience = [2, 6, 3, 1]
result = min_training_hours(5, 3, energy, experience)
print(result) # Output: 8public class CompetitionTraining {
public int minTrainingHours(int initialEnergy, int initialExperience, int[] energy, int[] experience) {
int hours = 0;
int currentEnergy = initialEnergy;
int currentExperience = initialExperience;
for (int i = 0; i < energy.length; i++) {
if (currentEnergy <= energy[i]) {
hours += (energy[i] - currentEnergy + 1);
currentEnergy = energy[i] + 1;
}
if (currentExperience <= experience[i]) {
hours += (experience[i] - currentExperience + 1);
currentExperience = experience[i] + 1;
}
currentEnergy -= energy[i];
currentExperience += experience[i];
}
return hours;
}
public static void main(String[] args) {
int[] energy = {1, 4, 3, 2};
int[] experience = {2, 6, 3, 1};
CompetitionTraining competition = new CompetitionTraining();
int result = competition.minTrainingHours(5, 3, energy, experience);
System.out.println(result); // Output: 8
}
}#include <vector>
#include <iostream>
int minTrainingHours(int initialEnergy, int initialExperience, std::vector<int>& energy, std::vector<int>& experience) {
int hours = 0;
int currentEnergy = initialEnergy;
int currentExperience = initialExperience;
for (size_t i = 0; i < energy.size(); i++) {
if (currentEnergy <= energy[i]) {
hours += (energy[i] - currentEnergy + 1);
currentEnergy = energy[i] + 1;
}
if (currentExperience <= experience[i]) {
hours += (experience[i] - currentExperience + 1);
currentExperience = experience[i] + 1;
}
currentEnergy -= energy[i];
currentExperience += experience[i];
}
return hours;
}
int main() {
std::vector<int> energy = {1, 4, 3, 2};
std::vector<int> experience = {2, 6, 3, 1};
int result = minTrainingHours(5, 3, energy, experience);
std::cout << result << std::endl; // Output: 8
return 0;
}function minTrainingHours(initialEnergy, initialExperience, energy, experience) {
let hours = 0;
let currentEnergy = initialEnergy;
let currentExperience = initialExperience;
for (let i = 0; i < energy.length; i++) {
if (currentEnergy <= energy[i]) {
hours += (energy[i] - currentEnergy + 1);
currentEnergy = energy[i] + 1;
}
if (currentExperience <= experience[i]) {
hours += (experience[i] - currentExperience + 1);
currentExperience = experience[i] + 1;
}
currentEnergy -= energy[i];
currentExperience += experience[i];
}
return hours;
}
const energy = [1, 4, 3, 2];
const experience = [2, 6, 3, 1];
const result = minTrainingHours(5, 3, energy, experience);
console.log(result); // Output: 8#include <stdio.h>
int minTrainingHours(int initialEnergy, int initialExperience, int* energy, int* experience, int n) {
int hours = 0;
int currentEnergy = initialEnergy;
int currentExperience = initialExperience;
for (int i = 0; i < n; i++) {
if (currentEnergy <= energy[i]) {
hours += (energy[i] - currentEnergy + 1);
currentEnergy = energy[i] + 1;
}
if (currentExperience <= experience[i]) {
hours += (experience[i] - currentExperience + 1);
currentExperience = experience[i] + 1;
}
currentEnergy -= energy[i];
currentExperience += experience[i];
}
return hours;
}
int main() {
int energy[] = {1, 4, 3, 2};
int experience[] = {2, 6, 3, 1};
int n = sizeof(energy) / sizeof(energy[0]);
int result = minTrainingHours(5, 3, energy, experience, n);
printf("%d\n", result); // Output: 8
return 0;
}using System;
public class Training {
public int MinTrainingHours(int initialEnergy, int initialExperience, int[] energy, int[] experience) {
int hours = 0;
int currentEnergy = initialEnergy;
int currentExperience = initialExperience;
for (int i = 0; i < energy.Length; i++) {
if (currentEnergy <= energy[i]) {
hours += (energy[i] - currentEnergy + 1);
currentEnergy = energy[i] + 1;
}
if (currentExperience <= experience[i]) {
hours += (experience[i] - currentExperience + 1);
currentExperience = experience[i] + 1;
}
currentEnergy -= energy[i];
currentExperience += experience[i];
}
return hours;
}
public static void Main() {
int[] energy = {1, 4, 3, 2};
int[] experience = {2, 6, 3, 1};
Training training = new Training();
Console.WriteLine(training.MinTrainingHours(5, 3, energy, experience)); // Output: 8
}
}This Python code uses a loop to adjust currentEnergy and currentExperience based on the opponents, similar to other languages. It performs the training increment calculations and updates accordingly.
Time Complexity: O(n) for the length of the input arrays.
Space Complexity: O(1) since it doesn't utilize extra data structures.
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 fordx + 1 - xhours to increase our energy todx + 1. - If
y leq dy, then we need to train fordy + 1 - yhours to increase our experience tody + 1. - Then, we subtract
dxfrom our energy and adddyto 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).
function minNumberOfHours(x: number, y: number, energy: number[], experience: number[]): number {
let ans = 0;
for (let i = 0; i < energy.length; ++i) {
const [dx, dy] = [energy[i], experience[i]];
if (x <= dx) {
ans += dx + 1 - x;
x = dx + 1;
}
if (y <= dy) {
ans += dy + 1 - y;
y = dy + 1;
}
x -= dx;
y += dy;
}
return ans;
}func minNumberOfHours(x int, y int, energy []int, experience []int) (ans int) {
for i, dx := range energy {
dy := experience[i]
if x <= dx {
ans += dx + 1 - x
x = dx + 1
}
if y <= dy {
ans += dy + 1 - y
y = dy + 1
}
x -= dx
y += dy
}
return
}impl Solution {
pub fn min_number_of_hours(
mut x: i32,
mut y: i32,
energy: Vec<i32>,
experience: Vec<i32>,
) -> i32 {
let mut ans = 0;
for (&dx, &dy) in energy.iter().zip(experience.iter()) {
if x <= dx {
ans += dx + 1 - x;
x = dx + 1;
}
if y <= dy {
ans += dy + 1 - y;
y = dy + 1;
}
x -= dx;
y += dy;
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Training Approach | Time Complexity: O(n) for the length of the input arrays. |
| Greedy + Simulation | – |
Complexity analysis
| 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 |
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.