Taking Maximum Energy From the Mystic Dungeon
MedPrompt
In a mystic dungeon, n magicians are standing in a line. Each magician has an attribute that gives you energy. Some magicians can give you negative energy, which means taking energy from you.
You have been cursed in such a way that after absorbing energy from magician i, you will be instantly transported to magician (i + k). This process will be repeated until you reach the magician where (i + k) does not exist.
In other words, you will choose a starting point and then teleport with k jumps until you reach the end of the magicians' sequence, absorbing all the energy during the journey.
You are given an array energy and an integer k. Return the maximum possible energy you can gain.
Note that when you are reach a magician, you must take energy from them, whether it is negative or positive energy.
Example 1:
Input: energy = [5,2,-10,-5,1], k = 3
Output: 3
Explanation: We can gain a total energy of 3 by starting from magician 1 absorbing 2 + 1 = 3.
Example 2:
Input: energy = [-2,-3,-1], k = 2
Output: -1
Explanation: We can gain a total energy of -1 by starting from magician 2.
Constraints:
1 <= energy.length <= 105-1000 <= energy[i] <= 10001 <= k <= energy.length - 1
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. We consider every possible magician from index 0 to n-1 as a starting point. For each starting point, we calculate the total energy by following the path of jumps of size k and summing the energy values until we go past the end of the line of magicians. We maintain a variable to keep track of the maximum energy found so far across all paths.
Algorithm
- Initialize a variable
maxEnergyto a very small number (e.g.,Integer.MIN_VALUE). - Iterate through each index
ifrom0ton-1to consider it as a starting point. - For each
i, initializecurrentEnergy = 0. - Start a simulation from
j = i. Whilejis a valid index (j < n):- Add
energy[j]tocurrentEnergy. - Update
jtoj + k.
- Add
- After the simulation for
iis done, updatemaxEnergy = max(maxEnergy, currentEnergy). - Return
maxEnergyafter checking all starting points.
Walkthrough
The algorithm works as follows:
- Initialize a variable
maxEnergyto the smallest possible integer value to ensure any calculated energy will be greater. - Loop through each index
ifrom0ton-1. Eachirepresents a potential starting point for our journey. - Inside this loop, for each starting index
i, initialize acurrentEnergyvariable to0. - Start another loop or a simulation process with a pointer
j, initialized toi. - This inner loop continues as long as
jis a valid index (i.e.,j < n). In each step of this inner loop, we add the energy of the magician atenergy[j]tocurrentEnergyand then updatejby addingkto it, simulating the teleportation. - Once the inner loop finishes (meaning we've jumped out of bounds),
currentEnergyholds the total energy for the path that started ati. - We then compare
currentEnergywithmaxEnergyand updatemaxEnergyifcurrentEnergyis larger. - After the outer loop has finished checking all possible starting points from
0ton-1, themaxEnergyvariable will hold the maximum possible energy that can be gained, which is our answer.
class Solution { public int maximumEnergy(int[] energy, int k) { int n = energy.length; int maxEnergy = Integer.MIN_VALUE; for (int i = 0; i < n; i++) { int currentEnergy = 0; int j = i; while (j < n) { currentEnergy += energy[j]; j += k; } if (currentEnergy > maxEnergy) { maxEnergy = currentEnergy; } } return maxEnergy; }}Complexity
Time
O(N * N/k). The outer loop runs `N` times (where `N` is `energy.length`). The inner `while` loop's iterations depend on the starting point `i` and `k`, running about `(N-i)/k` times. In the worst-case scenario (e.g., `k=1`), the complexity approaches O(N^2).
Space
O(1), as we only use a few variables to store the current and maximum energy, regardless of the input size.
Trade-offs
Pros
Simple to understand and implement as it directly models the problem statement.
Uses constant extra space.
Cons
Highly inefficient for large inputs, especially when
kis small.Likely to cause a 'Time Limit Exceeded' error on competitive programming platforms.
The brute-force approach involves redundant calculations. The total energy from a path starting at i is simply energy[i] plus the total energy from the path starting at i+k. This property of overlapping subproblems and optimal substructure is a perfect fit for dynamic programming. We can define dp[i] as the total energy gained starting from magician i. The recurrence relation is dp[i] = energy[i] + dp[i+k]. Since dp[i] depends on a value at a larger index (i+k), we should compute the dp values by iterating backward from the end of the array.
Algorithm
- Create a
dparray of sizen. - Iterate backward from
i = n-1down to0. - For each
i, calculatedp[i]using the recurrence:- If
i + k >= n, thendp[i] = energy[i]. - If
i + k < n, thendp[i] = energy[i] + dp[i+k].
- If
- After filling the
dparray, find the maximum value in it. This maximum value is the answer.
Walkthrough
This approach uses a DP table to store the results of subproblems to avoid re-computation.
- We create an auxiliary array,
dp, of the same size as theenergyarray.dp[i]will store the total energy of a path that begins at indexi. - We iterate backward through the
energyarray, from indexi = n-1down to0. - For each index
i, we computedp[i]based on our recurrence relation:- The next magician in the sequence would be at index
i + k. - If
i + kis outside the array bounds (>= n), it means the path starting atihas only one magician. Thus,dp[i] = energy[i]. - If
i + kis a valid index, the total energy is the sum of the current magician's energy and the total energy from the rest of the path. Since we are iterating backward, the value for the path starting ati+khas already been computed and stored indp[i+k]. Therefore,dp[i] = energy[i] + dp[i+k].
- The next magician in the sequence would be at index
- After the loop completes, the
dparray is fully populated, with eachdp[i]holding the total energy for a path starting ati. The final answer is the maximum value found within thisdparray.
class Solution { public int maximumEnergy(int[] energy, int k) { int n = energy.length; int[] dp = new int[n]; for (int i = n - 1; i >= 0; i--) { if (i + k >= n) { dp[i] = energy[i]; } else { dp[i] = energy[i] + dp[i + k]; } } int maxEnergy = Integer.MIN_VALUE; for (int totalEnergy : dp) { if (totalEnergy > maxEnergy) { maxEnergy = totalEnergy; } } return maxEnergy; }}Complexity
Time
O(N). We perform a single pass backward to fill the `dp` array (`O(N)`) and another pass to find the maximum value in it (`O(N)`). This results in a total linear time complexity.
Space
O(N), where `N` is the length of the `energy` array. This is due to the extra `dp` array we use to store the results.
Trade-offs
Pros
Efficient time complexity, making it suitable for large inputs.
Avoids redundant calculations present in the brute-force method.
Cons
Requires extra space proportional to the input size, which could be an issue for very large inputs in memory-constrained systems.
This approach builds upon the dynamic programming solution by optimizing its space complexity. Observing the DP recurrence dp[i] = energy[i] + dp[i+k], we see that to compute the value for index i, we only need the value at index i+k. Since our backward iteration ensures that the value for i+k is computed before i, we don't need a separate dp array. We can reuse the input energy array itself to store the DP values, effectively performing the computation in-place.
Algorithm
- Iterate backward through the
energyarray fromi = n-1down to0. - For each
i, ifi + k < n, updateenergy[i]by addingenergy[i+k]to it. This works becauseenergy[i+k]would have already been updated to hold the total path sum from that point. - After the first loop, the
energyarray is transformed such thatenergy[i]holds the total path sum starting ati. - Iterate through the modified
energyarray to find and return the maximum value.
Walkthrough
The in-place dynamic programming approach refines the previous method by eliminating the need for an extra array.
- Instead of creating a new
dparray, we use the inputenergyarray to store the total path sums. The goal is to transformenergysuch thatenergy[i]will hold the total energy for a path starting at indexi. - We iterate backward through the
energyarray, fromi = n-1down to0. - For each index
i, we check if a jump from this position is possible. Ifi + k < n, it means the path continues. The value atenergy[i+k]has, at this point in the backward iteration, already been updated to represent the total energy of the path starting fromi+k. We can therefore update the current element by adding this pre-calculated sum:energy[i] = energy[i] + energy[i+k]. - If
i + k >= n, the path starts and ends ati, soenergy[i]already represents the total sum for this path, and no action is needed. - After this loop finishes, the
energyarray is fully updated. The value at each indexiis now the total energy for a path starting at that index. - A final pass through the modified
energyarray is made to find the maximum value, which is the solution to the problem.
class Solution { public int maximumEnergy(int[] energy, int k) { int n = energy.length; // Iterate backwards. For each index i, the total energy of the path // starting at i+k has already been computed and stored in energy[i+k]. for (int i = n - 1; i >= 0; i--) { if (i + k < n) { energy[i] += energy[i + k]; } } // The modified energy array now holds the total energy for each starting point. // Find the maximum value in this array. int maxEnergy = Integer.MIN_VALUE; for (int totalEnergy : energy) { maxEnergy = Math.max(maxEnergy, totalEnergy); } return maxEnergy; }}Complexity
Time
O(N). The solution involves two separate passes over the array: one to update the values in-place and another to find the maximum. Both are linear operations, resulting in an overall `O(N)` time complexity.
Space
O(1). The algorithm modifies the input array in-place and does not require any additional data structures that scale with the input size.
Trade-offs
Pros
Optimal time complexity of O(N).
Optimal space complexity of O(1), making it very memory-efficient.
It is the most efficient solution for this problem.
Cons
This approach modifies the input array. If the original array must be preserved, a copy should be made first, which would negate the space optimization.
Solutions
Solution
class Solution {public int maximumEnergy(int[] energy, int k) { int ans = -(1 << 30); int n = energy.length; for (int i = n - k; i < n; ++i) { for (int j = i, s = 0; j >= 0; j -= k) { s += energy[j]; ans = Math.max(ans, s); } } return ans; }}class Solution {public: int maximumEnergy(vector<int> &energy, int k) { int ans = -(1 << 30); int n = energy.size(); for (int i = n - k; i < n; ++i) { for (int j = i, s = 0; j >= 0; j -= k) { s += energy[j]; ans = max(ans, s); } } return ans; }};class Solution: def maximumEnergy(self, energy: List[int], k: int) -> int: ans = - inf n = len(energy) for i in range(n - k, n): j, s = i, 0 while j >= 0: s += energy[j] ans = max(ans, s) j -= k return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.