Watch 10 video solutions for Taking Maximum Energy From the Mystic Dungeon, a medium level problem involving Array, Prefix Sum. This walkthrough by codestorywithMIK has 4,016 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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
Problem Overview: You are given an energy array representing energy gained or lost at each dungeon cell. From any starting index i, you repeatedly jump forward by k positions (i, i+k, i+2k...) until leaving the array. The task is to choose the best starting position that maximizes the total collected energy.
Approach 1: Brute Force Simulation (O(n^2 / k) time, O(1) space)
Try every index as a starting point. For each start i, simulate the jumps: repeatedly add energy[j] and move to j += k until you exit the array. Track the maximum total encountered. The logic is straightforward and mirrors the problem statement directly. However, many jump sequences overlap, so the same partial paths get recomputed multiple times, making it inefficient for large arrays.
Approach 2: Prefix-DP with Hash Map (O(n) time, O(k) space)
The key observation: indices that share the same remainder i % k belong to the same jump chain. If you start at index i, the next position is i + k, which has the same remainder. Instead of recomputing each chain repeatedly, process the array from right to left and store the best cumulative energy for each remainder group in a hash map. For each index, compute current = energy[i] + max(0, best[i % k]). This works like a rolling prefix sum or dynamic programming accumulation along the jump path. Update the map with the best value for that remainder and track the global maximum.
This approach avoids repeated traversal of the same chains. Each index contributes once, and the hash lookup provides the best continuation instantly. Conceptually it behaves like a one‑dimensional DP over grouped indices.
Recommended for interviews: The brute force version demonstrates that you understand the jumping pattern. Interviewers expect the optimized solution that groups indices by i % k and reuses computed results. Using a hash map (or array of size k) with a rolling accumulation shows strong understanding of array traversal and dynamic prefix-style aggregation techniques.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n^2 / k) | O(1) | Good for understanding the jump pattern or small inputs |
| Prefix-DP with Hash Map | O(n) | O(k) | Best general solution; avoids recomputation by grouping indices by modulo |