LeetCode 2383 - Minimum Hours of Training to Win a Competition

LeetCode Problem 2383

Difficulty: 🟢 Easy
Topics: Array, Greedy

Solution

Problem Understanding

The problem gives us two starting values, initialEnergy and initialExperience, which represent the player's stats before entering a sequence of competitions. We are also given two arrays, energy and experience, where each index corresponds to an opponent.

To defeat opponent i, the player must satisfy two strict conditions at the moment the fight begins:

• Current energy must be strictly greater than energy[i]
• Current experience must be strictly greater than experience[i]

After defeating an opponent:

• The player's energy decreases by energy[i]
• The player's experience increases by experience[i]

Before the competition begins, the player may train for any number of hours. Each hour of training can increase either energy or experience by exactly 1. The goal is to determine the minimum total number of training hours required so that the player can defeat every opponent in order.

The key detail is that the fights happen sequentially. Energy decreases permanently during the competition, while experience grows after every victory. Because experience accumulates over time, it may not be necessary to train enough to beat every opponent individually from the start.

The constraints are small:

• n <= 100
• All values are at most 100

These constraints mean that even straightforward simulations are efficient enough. We do not need advanced optimization techniques or sophisticated data structures.

Several edge cases are important:

• The player may already have enough energy and experience, requiring zero training.
• Because the condition is strictly greater than, equality is not sufficient. If current energy equals the opponent's energy, one more training hour is required.
• Energy continuously decreases, so we must ensure enough total energy to survive all battles.
• Experience increases after each win, so early training may eliminate the need for later training.

Approaches

Brute Force Approach

A brute-force approach would simulate different amounts of training and test whether the player can defeat all opponents. For example, we could repeatedly increase energy or experience hour by hour until the simulation succeeds.

The simulation itself is simple:

1. Start with the current energy and experience.
2. Process opponents in order.
3. If either stat is not strictly greater than the opponent's stat, the simulation fails.
4. Otherwise, update energy and experience after the battle.

This approach is correct because it directly checks whether a chosen amount of training works. However, trying all possible training distributions is inefficient and unnecessary. Even though the constraints are small, exploring all combinations of energy and experience increases would grow quickly.

Optimal Greedy Approach

The important observation is that energy and experience can be handled independently.

For energy:

• Every battle consumes energy permanently.
• To defeat all opponents, the initial energy must be strictly greater than the total energy consumed.

If the sum of all opponent energies is totalEnergy, then we need:

$$initialEnergy + trainedEnergy > totalEnergy$$

Therefore:

$$trainedEnergy = \max(0, totalEnergy + 1 - initialEnergy)$$

For experience:

• Experience increases after every victory.
• We can process opponents sequentially and only train when necessary.

At each opponent:

• If current experience is not strictly greater than the opponent's experience, train just enough to make it one larger.
• Then defeat the opponent and gain their experience.

This greedy strategy is optimal because training more than necessary at any step can never reduce future training requirements.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(K × n)	O(1)	Try multiple training distributions and simulate battles
Optimal	O(n)	O(1)	Compute required energy directly and greedily handle experience

Here, K represents the number of candidate training configurations explored by the brute-force method.

Algorithm Walkthrough

1. Compute the total energy required to survive all battles.

Since energy only decreases during fights, the player must start with strictly more energy than the sum of all opponent energies. 2. Calculate additional energy training hours.

If initialEnergy is already greater than the total required energy, no energy training is needed. Otherwise, train enough so that:

$$currentEnergy = totalEnergy + 1$$ 3. Initialize the current experience.

Set a variable to track the player's current experience during the competition. 4. Process opponents one by one.

For each opponent:

• Check whether current experience is strictly greater than the opponent's experience.
• If not, compute how many extra hours are needed:

$$needed = opponentExperience - currentExperience + 1$$

• Add this value to the answer.
• Increase current experience accordingly.

5. Simulate defeating the opponent.

After winning the fight, increase current experience by the opponent's experience value. 6. Return the total training hours.

Why it works

The algorithm works because the two resources behave differently.

Energy only decreases, so the only thing that matters is the total amount required across all fights. Having extra energy earlier provides no additional strategic advantage beyond surviving the sequence.

Experience, however, grows after each victory. The greedy strategy of training only when necessary is optimal because any extra training performed earlier could simply be postponed until it becomes required. Therefore, the minimum total training is achieved by adding exactly the missing amount at each step.

Python Solution

from typing import List

class Solution:
    def minNumberOfHours(
        self,
        initialEnergy: int,
        initialExperience: int,
        energy: List[int],
        experience: List[int]
    ) -> int:
        
        total_training_hours = 0

        # Energy requirement
        total_energy_needed = sum(energy)

        if initialEnergy <= total_energy_needed:
            total_training_hours += (
                total_energy_needed + 1 - initialEnergy
            )

        # Experience requirement
        current_experience = initialExperience

        for opponent_experience in experience:
            if current_experience <= opponent_experience:
                extra_training = (
                    opponent_experience - current_experience + 1
                )

                total_training_hours += extra_training
                current_experience += extra_training

            current_experience += opponent_experience

        return total_training_hours

The implementation begins by calculating the total energy needed for all battles. Since the player must always have strictly greater energy before every fight, the required starting energy is one greater than the total energy consumption.

Next, the code handles experience greedily. The variable current_experience tracks the player's experience throughout the competition.

For each opponent:

• If current experience is insufficient, the code computes the exact number of training hours required to make it strictly larger.
• Those training hours are added to the answer.
• The player's experience is updated.
• After defeating the opponent, the opponent's experience is added to the player's experience.

This directly mirrors the algorithm described earlier.

Go Solution

package main

func minNumberOfHours(initialEnergy int, initialExperience int, energy []int, experience []int) int {
	totalTrainingHours := 0

	// Energy requirement
	totalEnergyNeeded := 0
	for _, value := range energy {
		totalEnergyNeeded += value
	}

	if initialEnergy <= totalEnergyNeeded {
		totalTrainingHours += totalEnergyNeeded + 1 - initialEnergy
	}

	// Experience requirement
	currentExperience := initialExperience

	for _, opponentExperience := range experience {
		if currentExperience <= opponentExperience {
			extraTraining := opponentExperience - currentExperience + 1

			totalTrainingHours += extraTraining
			currentExperience += extraTraining
		}

		currentExperience += opponentExperience
	}

	return totalTrainingHours
}

The Go implementation follows the same logic as the Python version.

A few Go-specific details are worth noting:

• Go slices are used for the energy and experience arrays.
• Integer overflow is not a concern because all values are very small.
• No special handling for nil slices is necessary because the problem guarantees valid input arrays.
• The implementation uses range loops for concise iteration.

Worked Examples

Example 1

Input:

initialEnergy = 5
initialExperience = 3
energy = [1,4,3,2]
experience = [2,6,3,1]

Step 1: Energy Calculation

Value	Result
Sum of energy array	10
Required starting energy	11
Initial energy	5
Extra energy training	6

Current answer:

training = 6

Step 2: Experience Simulation

Opponent	Current Experience Before Fight	Opponent Experience	Extra Training Needed	Current Experience After Fight
0	3	2	0	5
1	5	6	2	13
2	13	3	0	16
3	16	1	0	17

Total experience training:

2

Final answer:

6 + 2 = 8

Example 2

Input:

initialEnergy = 2
initialExperience = 4
energy = [1]
experience = [3]

Step 1: Energy Calculation

Value	Result
Sum of energy array	1
Required starting energy	2
Initial energy	2
Extra energy training	0

Because the requirement is strictly greater before the fight, having energy 2 against opponent energy 1 is sufficient.

Step 2: Experience Simulation

Opponent	Current Experience Before Fight	Opponent Experience	Extra Training Needed	Current Experience After Fight
0	4	3	0	7

Final answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We traverse the arrays once
Space	O(1)	Only a few variables are used

The algorithm performs a single pass through the opponents while maintaining running totals for energy and experience. No additional data structures proportional to input size are required.

Test Cases

from typing import List

class Solution:
    def minNumberOfHours(
        self,
        initialEnergy: int,
        initialExperience: int,
        energy: List[int],
        experience: List[int]
    ) -> int:
        
        total_training_hours = 0

        total_energy_needed = sum(energy)

        if initialEnergy <= total_energy_needed:
            total_training_hours += (
                total_energy_needed + 1 - initialEnergy
            )

        current_experience = initialExperience

        for opponent_experience in experience:
            if current_experience <= opponent_experience:
                extra_training = (
                    opponent_experience - current_experience + 1
                )

                total_training_hours += extra_training
                current_experience += extra_training

            current_experience += opponent_experience

        return total_training_hours

solution = Solution()

assert solution.minNumberOfHours(
    5, 3, [1,4,3,2], [2,6,3,1]
) == 8  # provided example 1

assert solution.minNumberOfHours(
    2, 4, [1], [3]
) == 0  # provided example 2

assert solution.minNumberOfHours(
    1, 1, [1], [1]
) == 2  # needs one energy and one experience training

assert solution.minNumberOfHours(
    100, 100, [1,1,1], [1,1,1]
) == 0  # already stronger than all opponents

assert solution.minNumberOfHours(
    5, 1, [1,1,1], [10,20,30]
) == 10  # large early experience training

assert solution.minNumberOfHours(
    3, 2, [1,1], [1,1]
) == 0  # exact minimum sufficient values

assert solution.minNumberOfHours(
    2, 2, [1,1], [1,1]
) == 1  # only energy training needed

assert solution.minNumberOfHours(
    10, 1, [1,2,3], [1,2,3]
) == 1  # only experience training needed

assert solution.minNumberOfHours(
    1, 50, [1,1,1,1], [1,1,1,1]
) == 5  # only energy deficiency

assert solution.minNumberOfHours(
    5, 5, [4], [10]
) == 6  # strict experience inequality check

Test	Why
Example 1	Validates the standard mixed training scenario
Example 2	Confirms zero training case
Single opponent with equal stats	Verifies strict inequality handling
Very large initial stats	Ensures no unnecessary training
Large experience gaps	Tests repeated experience updates
Exact sufficient values	Confirms correct boundary behavior
Only energy deficit	Isolates energy logic
Only experience deficit	Isolates experience logic
Multiple energy reductions	Tests cumulative energy requirement
Experience equality edge case	Ensures > rather than >=

Edge Cases

One important edge case occurs when the player's stats are exactly equal to an opponent's stats. The problem requires the player's values to be strictly greater, not greater than or equal. This can easily introduce off-by-one errors. The implementation handles this correctly by checking <= and adding +1 when computing required training.

Another important case is when the player already has sufficient energy and experience to defeat every opponent. A careless implementation might still add unnecessary training because it does not properly check the conditions before increasing values. This solution avoids that by only training when the current value is insufficient.

A third edge case involves large experience jumps early in the competition. Suppose the player starts with very low experience but defeating one strong opponent grants enough experience for all later fights. A naive approach might overestimate training by considering opponents independently. The greedy simulation correctly accounts for accumulated experience after every victory, ensuring only the minimum necessary training is added.