Is Taking Maximum Energy From the Mystic Dungeon easy or hard?

Taking Maximum Energy From the Mystic Dungeon is generally rated Medium. The brute force idea is simple, but recognizing that indices with the same i % k share the same jump chain and can reuse computed sums requires a dynamic programming insight.

Taking Maximum Energy From the Mystic Dungeon Python/Java solution

Most implementations compute values from right to left and store the best energy per remainder group. Python typically uses a dictionary or list of size k, while Java and C++ often use arrays for faster lookups. The logic remains the same and runs in O(n) time.

How to solve Taking Maximum Energy From the Mystic Dungeon in O(n)?

Traverse the array from right to left while tracking the best cumulative energy for each index remainder i % k. For each position compute current = energy[i] + max(0, best[i % k]). Update the stored value and maintain the global maximum. Each element is processed once, producing an O(n) algorithm.

What is the best approach for Taking Maximum Energy From the Mystic Dungeon?

The optimal solution groups indices by their modulo with k and processes the array from right to left. A hash map (or array of size k) stores the best cumulative energy for each remainder group. Each index computes energy[i] plus the best continuation for the same remainder, giving an O(n) time and O(k) space solution.

Is Taking Maximum Energy From the Mystic Dungeon asked at Google/Amazon/Meta?

Problems involving jump patterns, prefix-style accumulation, and dynamic programming on arrays frequently appear in interviews at companies like Amazon and Google. Variants that group indices by modulo or reuse computed path sums are common interview patterns.

What data structure is used in Taking Maximum Energy From the Mystic Dungeon?

The optimized solution uses a hash map (or a fixed array of size k) to store the best cumulative energy for each remainder class. The algorithm also relies on simple array traversal and dynamic programming style accumulation along jump chains.

What is the time complexity of Taking Maximum Energy From the Mystic Dungeon?

The brute force simulation runs in about O(n^2 / k) time because each starting position may traverse a long jump chain. The optimized approach processes each element once and performs constant-time hash lookups, giving O(n) time complexity with O(k) extra space.

Description Hints 2 Solution Video 18:30

3147. Taking Maximum Energy From the Mystic Dungeon

Medium61.0% acceptance5 companies

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 <= 10⁵
-1000 <= energy[i] <= 1000
1 <= k <= energy.length - 1

Asked at 5 companies

IBM JPMorgan Chase Bloomberg

Google Amazon

Topics

Array Prefix Sum

Hints open one at a time

Hint 1

Let dp[i] denote the energy we gain starting from index i.

Hint 2

We can notice, that dp[i] = dp[i + k] + energy[i].

18:30

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def maximumEnergy(self, energy: List[int], k: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[5,2,-10,-5,1]
3

Input

[-2,-3,-1]
2

Your code is saved on this device.Solution