Frontend School

Gem Collector with Supercharge

DSA
medium

Gem Collector with Supercharge

Medium
Dynamic Programming
2D DP
Grid

Overview

You are a lead game designer for "Gemstone Odyssey," a popular mobile game. Players navigate a grid-based map, collecting valuable gems. To introduce a new layer of strategy and excitement, you've decided to implement a "Supercharge" ability. This ability allows players to temporarily double the value of gems collected from a specific cell, but it can only be used a limited number of times per level. Your task is to design an algorithm that determines the maximum total gem value a player can collect when traversing a given level grid.

What you need to do / Task

Given a 2D grid representing a level map, where each cell (r, c) contains a certain number of gems, and an integer k representing the total number of Supercharge abilities available, find the maximum total gem value a player can collect.

Players start at the top-left cell (0, 0) and must reach the bottom-right cell (M-1, N-1). From any cell (r, c), a player can only move one step right to (r, c+1) or one step down to (r+1, c).

When a player lands on a cell (r, c), they collect the gems from that cell. If they choose to use a Supercharge ability on that cell, the collected gem value from grid[r][c] is doubled. Each Supercharge ability can be used only once.

Input & output

The function maxGems will take the following parameters:

  • grid: A number[][] representing the level map. grid[r][c] is the number of gems in cell (r, c).
  • k: A number representing the total number of Supercharge abilities available.

The function should return a number representing the maximum total gem value that can be collected.

Clarifications

  • Grid Dimensions: The grid will always have at least one row and one column.
  • Gem Values: All gem values in the grid will be non-negative integers.
  • Supercharge Usage: You can use a Supercharge on any cell you visit, including the starting cell (0,0) and the ending cell (M-1, N-1), as long as you have k > 0 abilities remaining.
  • Path Uniqueness: You only collect gems from a cell once, upon landing on it. The path is unique (no cycles, only right/down moves).

Examples

1

Example 1

Input:

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

Output:

33

Note:

Consider all paths and supercharge options: Path 1: (0,0) -> (0,1) -> (1,1). Cells visited: 10, 5, 8.

  • Supercharge (0,0): 2*10 + 5 + 8 = 33
  • Supercharge (0,1): 10 + 2*5 + 8 = 28
  • Supercharge (1,1): 10 + 5 + 2*8 = 31 Path 2: (0,0) -> (1,0) -> (1,1). Cells visited: 10, 2, 8.
  • Supercharge (0,0): 2*10 + 2 + 8 = 30
  • Supercharge (1,0): 10 + 2*2 + 8 = 22
  • Supercharge (1,1): 10 + 2 + 2*8 = 28 The maximum among all options is 33.
2

Example 2

Input:

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

Output:

104

Note:

Since k=0, no supercharges can be used. We need to find the path that maximizes the sum of original gem values. The path (0,0) -> (1,0) -> (1,1) -> (2,1) -> (2,2) visits cells with values 1, 1, 100, 1, 1, totaling 104.

3

Example 3

Input:

grid = [[1, 1, 1], [1, 1, 1], [1, 1, 1]], k = 2

Output:

7

Note:

An optimal path will always visit 5 cells (e.g., (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2)). With all gem values being 1, and 2 supercharges available, we can double two of these values. This yields 3 * 1 (normal) + 2 * (2*1) (supercharged) = 3 + 4 = 7.

Constraints

Constraints & assumptions

  • 1 <= grid.length <= 500 (M rows)
  • 1 <= grid[0].length <= 500 (N columns)
  • 0 <= grid[r][c] <= 1000
  • 0 <= k <= 10

Out of scope

  • Handling invalid inputs (e.g., grid being null or empty, k being negative). Assume valid inputs per constraints.
  • Reconstructing the optimal path; only the maximum total gem value is required.
  • Movement other than right or down (e.g., diagonal, up, left).

What interviewers evaluate

  • Correctness: The solution should accurately calculate the maximum gem value for all valid inputs, including edge cases.
  • Efficiency: The solution should demonstrate optimal time and space complexity, leveraging dynamic programming effectively.
  • Clarity: The code should be well-structured, readable, and easy to understand, reflecting good software engineering practices.
  • Problem-Solving: The candidate's ability to identify the dynamic programming structure, define the state, and formulate correct transitions.

Loading editor...