Taking Maximum Energy From the Mystic Dungeon - Solution & Explanation
Problem Statement
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
​​​​​​
Approach Overview
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 1: Brute Force Approach
The brute force approach involves iterating over all possible solutions and checking which one satisfies the condition of the problem. This might not be optimal in terms of efficiency but is straightforward to implement.
solve function implements the brute force solution by iterating through possible combinations and checking each for the needed condition.
Complexity
Time Complexity: O(n^2)
Space Complexity: O(1)
Approach 2: Optimized Approach Using Hash Map
This approach leverages hash maps (or dictionaries) to achieve a more efficient solution. By storing already computed combinations, we reduce the number of operations significantly compared to brute force.
The function solve would use a hash map to track and compute results efficiently, significantly reducing the number of redundant calculations.
Complexity
Time Complexity: O(n)
Space Complexity: O(n)
Approach 3: Enumeration + Reverse Traversal
We can enumerate the endpoints within the range [n - k, n), then traverse backwards from each endpoint, accumulating the energy values of wizards at intervals of k, and update the answer.
The time complexity is O(n), where n is the length of array energy. The space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^2) |
| Optimized Approach Using Hash Map | Time Complexity: O(n) |
| Enumeration + Reverse Traversal | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Taking Maximum Energy From the Mystic Dungeon | 2 Approaches | Leetcode 3147 | codestorywithMIK • codestorywithMIK • 4,188 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Taking Maximum Energy From the Mystic Dungeon easy or hard?
Taking Maximum Energy From the Mystic Dungeon Python/Java solution
How to solve Taking Maximum Energy From the Mystic Dungeon in O(n)?
What is the best approach for Taking Maximum Energy From the Mystic Dungeon?
Is Taking Maximum Energy From the Mystic Dungeon asked at Google/Amazon/Meta?
What data structure is used in Taking Maximum Energy From the Mystic Dungeon?
What is the time complexity of Taking Maximum Energy From the Mystic Dungeon?
Ready to solve this problem?
Practice Taking Maximum Energy From the Mystic Dungeon with our built-in code editor and test cases.
Practice on FleetCode