Frontend School

Strategic Energy Collection

DSA
medium

Strategic Energy Collection

Medium
Dynamic Programming
2D DP
Grid

Overview

In the popular strategy game "Aetherium Ascent," players navigate a mystical grid to collect "Aether Energy." Your team is developing a new challenge mode where players must strategically utilize a limited number of "Energy Boost" items to maximize their total collected energy. This problem focuses on the core algorithmic challenge of finding the optimal path to achieve the highest possible energy score.

What you need to do / Task

Implement a function getMaxEnergy that calculates the maximum total energy a player can collect when moving through a grid from the top-left corner (0, 0) to the bottom-right corner (M-1, N-1).

The rules are as follows:

  1. You start at (0, 0) and must reach (M-1, N-1).
  2. From any cell (r, c), you can only move right to (r, c+1) or down to (r+1, c).
  3. Each cell (r, c) contains grid[r][c] energy points.
  4. You are given k "Energy Boost" items. When you pick up energy from a cell, you can choose to use an "Energy Boost" item on that specific cell. If you do, the energy collected from that cell is doubled (grid[r][c] * 2).
  5. Each "Energy Boost" item can only be used once. You can use at most k items throughout your path.
  6. The total energy collected is the sum of energy from all cells on your path, applying boosts where chosen.

Input & output

Function Signature: function getMaxEnergy(grid: number[][], k: number): number

  • grid: A 2D array of integers M x N, where grid[r][c] represents the energy points available at cell (r, c). All grid[r][c] values are non-negative.
  • k: An integer representing the maximum number of "Energy Boost" items you can use.

Return Value:

  • An integer representing the maximum total energy points that can be collected.

Clarifications

  • The grid will always have at least one row and one column (M >= 1, N >= 1).
  • All energy values grid[r][c] are non-negative.
  • It is always possible to reach (M-1, N-1) from (0,0) following the allowed moves.
  • k can be 0, meaning no boost items are available. k will not be negative.
  • The k items can be used on any cell of your path, including the start (0,0) and end (M-1, N-1) cells.

Examples

1

Example 1

Input:

grid = [[10, 5], [2, 8]], k = 0

Output:

23

Note:

With k=0, no boosts can be used. The path (0,0)->(0,1)->(1,1) yields 10+5+8=23. The path (0,0)->(1,0)->(1,1) yields 10+2+8=20. Maximum is 23.

2

Example 2

Input:

grid = [[1, 10], [100, 1]], k = 1

Output:

202

Note:

With k=1, we can use one boost. The path (0,0)->(1,0)->(1,1) visits cells with values (1, 100, 1). Boosting the value 100 at (1,0) yields 1 + (100*2) + 1 = 202. This is the maximum possible.

3

Example 3

Input:

grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9]], k = 2

Output:

46

Note:

Consider the path (0,0)->(1,0)->(2,0)->(2,1)->(2,2) which visits cells with values [1, 4, 7, 8, 9]. To maximize the score with 2 boosts, we would double the two largest values on this path, which are 8 and 9. This yields 1 + 4 + 7 + (82) + (92) = 1 + 4 + 7 + 16 + 18 = 46. Other paths and boost combinations would yield less.

Constraints

Constraints & assumptions

  • 1 <= M, N <= 50 (where M is number of rows, N is number of columns)
  • 0 <= grid[r][c] <= 1000
  • 0 <= k <= 10
  • The grid contains only integer values.

Out of scope

  • Handling invalid grid inputs (e.g., non-rectangular arrays, non-integer values).
  • Path reconstruction (only the maximum score is required).
  • Optimizing space complexity beyond O(M*N*K) if the candidate finds a correct solution within that complexity.

What interviewers evaluate

  • Algorithmic Correctness: The ability to identify and apply a correct dynamic programming approach to solve the problem, handling the state transitions and base cases accurately.
  • Edge Case Handling: Correctly managing boundary conditions, such as the first row/column and cases where k is 0 or very large.
  • Time and Space Complexity: Understanding and analyzing the time and space efficiency of the proposed solution.
  • Code Quality: Writing clean, readable, and well-structured code with appropriate variable naming and comments where necessary.

Loading editor...