Scale Engineer

Taking Maximum Energy From the Mystic Dungeon

Med
#2796Time: 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.1 company
Patterns
Prefix Sum
Data structures
Array
Companies
IBM

Prompt

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] <= 1000
  • 1 <= 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 maxEnergy to a very small number (e.g., Integer.MIN_VALUE).
  • Iterate through each index i from 0 to n-1 to consider it as a starting point.
  • For each i, initialize currentEnergy = 0.
  • Start a simulation from j = i. While j is a valid index (j < n):
    • Add energy[j] to currentEnergy.
    • Update j to j + k.
  • After the simulation for i is done, update maxEnergy = max(maxEnergy, currentEnergy).
  • Return maxEnergy after checking all starting points.

Walkthrough

The algorithm works as follows:

  1. Initialize a variable maxEnergy to the smallest possible integer value to ensure any calculated energy will be greater.
  2. Loop through each index i from 0 to n-1. Each i represents a potential starting point for our journey.
  3. Inside this loop, for each starting index i, initialize a currentEnergy variable to 0.
  4. Start another loop or a simulation process with a pointer j, initialized to i.
  5. This inner loop continues as long as j is a valid index (i.e., j < n). In each step of this inner loop, we add the energy of the magician at energy[j] to currentEnergy and then update j by adding k to it, simulating the teleportation.
  6. Once the inner loop finishes (meaning we've jumped out of bounds), currentEnergy holds the total energy for the path that started at i.
  7. We then compare currentEnergy with maxEnergy and update maxEnergy if currentEnergy is larger.
  8. After the outer loop has finished checking all possible starting points from 0 to n-1, the maxEnergy variable 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 k is small.

  • Likely to cause a 'Time Limit Exceeded' error on competitive programming platforms.

Solutions

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;  }}

Video 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.

← Previous

Previous problem

Next →

Next problem