LeetCode 3259 - Maximum Energy Boost From Two Drinks

LeetCode Problem 3259

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming

Solution

Problem Understanding

This problem is asking you to plan the consumption of two energy drinks over n hours to maximize the total energy boost. Each drink has a known energy contribution per hour, given by two arrays, energyDrinkA and energyDrinkB. You can drink only one energy drink per hour. However, if you switch from one drink to another, you must skip one hour to cleanse your system, during which you gain no energy. You can start with either drink.

The inputs represent the energy boost per hour from each drink. The output is a single integer, the maximum total energy boost achievable over all n hours. Constraints indicate that n can be large (up to 100,000) and energy values can also be large (up to 100,000 per hour), so a naive solution that tries every possible sequence of drink choices would be too slow. Edge cases include sequences where switching drinks is never beneficial, sequences where one drink is always better, and sequences where switching exactly once is optimal.

Approaches

Brute Force Approach

A brute-force approach would attempt all sequences of drinking A and B, considering the cleanse hour whenever a switch occurs. This could be implemented as a recursive solution that branches for every drink choice at each hour, skipping an hour when switching. While correct, this has exponential time complexity, O(2^n), because each hour can branch to either staying with the same drink or switching, which is clearly too slow for n up to 100,000.

Optimal Approach

The key observation is that this is a dynamic programming problem with three states at each hour: the maximum energy if you end the hour drinking A, drinking B, or skipping due to a switch. By keeping track of these three states, you can iteratively compute the maximum energy for each hour based on the previous hour's states, without enumerating all sequences. The recurrence is as follows:

• If you drink A at hour i, you either came from drinking A at hour i-1 (no switch) or from a skip after B at hour i-1 (switch).
• If you drink B at hour i, similar logic applies.
• If you skip at hour i, it comes from a switch from A or B at i-1.

This allows a linear O(n) solution with O(1) or O(n) space.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Recursively tries all sequences
Optimal	O(n)	O(1)	DP with three states per hour

Algorithm Walkthrough

1. Initialize three variables to track the maximum energy if the previous hour ended with drinking A (prevA), drinking B (prevB), or skipping (prevSkip).
2. Iterate over each hour i from 0 to n-1.
3. Compute the maximum energy for drinking A at hour i as the max of prevA + energyDrinkA[i] (continuing A) or prevSkip + energyDrinkA[i] (switch from B to A after skip).
4. Compute the maximum energy for drinking B at hour i similarly.
5. Compute the maximum energy for skipping at hour i as the max of prevA or prevB (since skipping follows a switch).
6. Update prevA, prevB, and prevSkip to the new values.
7. After processing all hours, return the maximum of prevA, prevB, and prevSkip.

Why it works: At each hour, the three states fully capture all possibilities for the current hour given the previous decisions. The algorithm guarantees that every possible valid sequence of drinks and skips is represented by some combination of these states.

Python Solution

from typing import List

class Solution:
    def maxEnergyBoost(self, energyDrinkA: List[int], energyDrinkB: List[int]) -> int:
        prevA, prevB, prevSkip = 0, 0, 0
        
        for a, b in zip(energyDrinkA, energyDrinkB):
            currA = max(prevA + a, prevSkip + a)
            currB = max(prevB + b, prevSkip + b)
            currSkip = max(prevA, prevB)
            prevA, prevB, prevSkip = currA, currB, currSkip
            
        return max(prevA, prevB, prevSkip)

The implementation directly follows the algorithm. prevA, prevB, and prevSkip store the best totals ending with each possible last action. At each hour, currA, currB, and currSkip are computed and then assigned back to the previous variables for the next iteration. This ensures O(1) space and linear runtime.

Go Solution

func maxEnergyBoost(energyDrinkA []int, energyDrinkB []int) int64 {
    var prevA, prevB, prevSkip int64
    
    for i := 0; i < len(energyDrinkA); i++ {
        a, b := int64(energyDrinkA[i]), int64(energyDrinkB[i])
        currA := max(prevA+a, prevSkip+a)
        currB := max(prevB+b, prevSkip+b)
        currSkip := max(prevA, prevB)
        prevA, prevB, prevSkip = currA, currB, currSkip
    }
    
    return max(prevA, prevB, prevSkip)
}

func max(x, y int64) int64 {
    if x > y {
        return x
    }
    return y
}

In Go, we use int64 to avoid potential integer overflow since energy values can be up to 10^5 and n can be up to 10^5. The logic is otherwise identical to Python, using a helper max function.

Worked Examples

Example 1: energyDrinkA = [1,3,1], energyDrinkB = [3,1,1]

Hour	prevA	prevB	prevSkip
0	1	3	0
1	4	1	3
2	5	4	4

Maximum is 5.

Example 2: energyDrinkA = [4,1,1], energyDrinkB = [1,1,3]

Hour	prevA	prevB	prevSkip
0	4	1	0
1	5	1	4
2	6	7	5

Maximum is 7.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Single pass through all hours
Space	O(1)	Only three state variables are maintained

The complexity is optimal given the constraints, and the algorithm handles sequences of up to 100,000 hours efficiently.

Test Cases

solution = Solution()

assert solution.maxEnergyBoost([1,3,1], [3,1,1]) == 5  # example 1
assert solution.maxEnergyBoost([4,1,1], [1,1,3]) == 7  # example 2
assert solution.maxEnergyBoost([1,1,1], [1,1,1]) == 3  # all equal
assert solution.maxEnergyBoost([100000]*5, [1]*5) == 500000  # large numbers
assert solution.maxEnergyBoost([1,2,3,4,5], [5,4,3,2,1]) == 15  # optimal switch in middle

Test	Why
[1,3,1],[3,1,1]	Matches example 1
[4,1,1],[1,1,3]	Matches example 2
[1,1,1],[1,1,1]	All equal values, test tie handling
[100000]*5,[1]*5	Tests large numbers and sum correctness
[1,2,3,4,5],[5,4,3,2,1]	Tests optimal switching logic

Edge Cases

One edge case is when all values in one drink array dominate the other. In this case, switching is never beneficial. The implementation correctly chooses the dominant drink each hour.

Another edge case is when alternating drinks yields higher energy, requiring careful handling of the skip hour. The DP approach naturally models this by including the skip state.

A third edge case is the smallest allowed input size, n=3. This is important because the logic of switching and skipping relies on having multiple hours. The algorithm correctly computes the maximum even for the minimum input size by initializing states to zero.